Prev: Dynamic cycle Detection
Next: VLSI chip testing in Introduction to Algorithm
From: peter.vanna on 26 Apr 2007 22:26
I have a question regarding the performance of the Dijkstra's
algorithm using different heap implementations.

Suppose that the size of the graphs is around 50 nodes to 250 nodes,
number of edges is around 50 to 300. Is it worth using Fibonacci heap
in the Dijkstra's algorithm or just using simple priority queue? Any
pointer?

Thank you.

From: Le Chaud Lapin on 7 May 2007 02:30
On Apr 26, 9:26 pm, peter.va...(a)gmail.com wrote:
> I have a question regarding the performance of the Dijkstra's
> algorithm using different heap implementations.
>
> Suppose that the size of the graphs is around 50 nodes to 250 nodes,
> number of edges is around 50 to 300. Is it worth using Fibonacci heap
> in the Dijkstra's algorithm or just using simple priority queue? Any
> pointer?

http://en.wikipedia.org/wiki/Fibonacci_heap

As always, "it depends." In this case, it depends on the sequence of
operations you intend to apply to the heaps. With Fibonacci heaps,
the amortized time of some operations is less than for binomial
heaps. However, there is the danger that the same operations could
run in linear time. As pointed out in the Wikipedia article, if the
possibility of an operation running in linear time is unacceptable,
you should not use a Fibonacci heap.

However, if these are you only two choices, then the answer is clear:
you must use a Fibonacci heap. The reason is that, contrary to
popular belief, it is not possible to implement Dijkstra's algorithm
using priority queues, at least not the kind you would find in a
typical book on data structures and algorithms. Such priority queues
do not support the operation of redefining the priority of elements as
use of the data structure progresses, which, as you know, is necessary
in the relaxation step of Dijkstra's algorithm.

-Le Chaud Lapin-

From: Googmeister on 7 May 2007 10:02
A *simple* priority queue is likely to be such fine for the
small graphs you are describing. And by simple I mean
just keep the keys and values in an unordered array or list.

Use a binary heap for larger networks, e.g., see Sedgewick's
Algorithms in X for efficient implementations (that do
support decrease-key).

Fibonacci heaps are primarily of theoretical interest and
are unlikely to improve performance in practice, except
on large, pathological networks.


Le Chaud Lapin wrote:
> On Apr 26, 9:26 pm, peter.va...(a)gmail.com wrote:
> > I have a question regarding the performance of the Dijkstra's
> > algorithm using different heap implementations.
> >
> > Suppose that the size of the graphs is around 50 nodes to 250 nodes,
> > number of edges is around 50 to 300. Is it worth using Fibonacci heap
> > in the Dijkstra's algorithm or just using simple priority queue? Any
> > pointer?
>
> http://en.wikipedia.org/wiki/Fibonacci_heap
>
> As always, "it depends." In this case, it depends on the sequence of
> operations you intend to apply to the heaps. With Fibonacci heaps,
> the amortized time of some operations is less than for binomial
> heaps. However, there is the danger that the same operations could
> run in linear time. As pointed out in the Wikipedia article, if the
> possibility of an operation running in linear time is unacceptable,
> you should not use a Fibonacci heap.
>
> However, if these are you only two choices, then the answer is clear:
> you must use a Fibonacci heap. The reason is that, contrary to
> popular belief, it is not possible to implement Dijkstra's algorithm
> using priority queues, at least not the kind you would find in a
> typical book on data structures and algorithms. Such priority queues
> do not support the operation of redefining the priority of elements as
> use of the data structure progresses, which, as you know, is necessary
> in the relaxation step of Dijkstra's algorithm.
>
> -Le Chaud Lapin-

From: wade on 7 May 2007 10:13
On May 7, 1:30 am, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote:
> However, if these are you only two choices, then the answer is clear:
> you must use a Fibonacci heap. The reason is that, contrary to
> popular belief, it is not possible to implement Dijkstra's algorithm
> using priority queues, at least not the kind you would find in a
> typical book on data structures and algorithms. Such priority queues
> do not support the operation of redefining the priority of elements as
> use of the data structure progresses, which, as you know, is necessary
> in the relaxation step of Dijkstra's algorithm.

As the wiki article on binomial heaps says, you can increase the
priority ("decrease key") in O(log n). That is sufficient for
Dijkstra's algorithm. You can also decrease an element's priority in
log n.

I'd say that in this case, "popular opinion" is correct. There are
certainly implementations of priority queues which won't work (C++
std::priority_queue), but binomial heaps are fine.

From: Le Chaud Lapin on 7 May 2007 13:22
On May 7, 9:13 am, w...(a)stoner.com wrote:
> As the wiki article on binomial heaps says, you can increase the
> priority ("decrease key") in O(log n). That is sufficient for
> Dijkstra's algorithm. You can also decrease an element's priority in
> log n.
>
> I'd say that in this case, "popular opinion" is correct. There are
> certainly implementations of priority queues which won't work (C++
> std::priority_queue), but binomial heaps are fine.

Well of course. For my implementation of Dijkstra's algorithm, I use
a data structure that does not yet have a name as far as I know. It
supports all the operations mentioned in O(log n) time, so naturally,
the underlying mechanism could be used to implement a priority queue.
However, one must take into consideration the state of mind of the OP,
who mentioned "simple priority queue". Since binomial, Fibonacci, (my
algorithm), etc..are 'all' implementations of priority queues, there
is the possibility that, by saying "simple priority queue", the OP
meant ones that are implemented using binary heaps.

Also, there are computer science texts that have sections on priority
queues implemented specifically using binary heaps, and in the same
section, declares that such priority queues can be used to implemente
Dijkstra's algorithm, which is not correct. IIRC, there is one text
by Denneberg and Lewis, Data Structures & Their Algorithm, that first
makes the statement, then makes an immediate disqualification by
saying something like...."actually, Dijkstra's algorithm has the
peculiar requirement of being able to modify priorities of the queue,
so you cannot use a standard binary heap." I forget the exact wording.

A novice reading this statement might be encourage into thinking that
the priority queues mentioned, the ones implemented using binary
heaps, only require a small bit of tweaking to support incremental
redefinition of priorities. This is not true. I would also imagine
that more than one non-novice has been mislead into thinking this
also, only to discover that there is no possibility for "tweaking".
Binary heaps simply will not support Dijkstra's algorithm. There is
nothing you can do by adding "boosting" structures like associative
sets and sets - the structure itself is what it is, not good for
redefinition of priorities. You have to use something else, like a
binomial heap or a Fibonacci heap, or something "other thing". ;)

This is why, in the sections of such books where it is clear that the
author is speaking of binary heap implementation of priorities, it
should not be mentioned, IMO, that they can be used to implement
Dijkstra's algorithm.

-Le Chaud Lapin-

 |  Next  |  Last
Pages: 1 2 3
Prev: Dynamic cycle Detection
Next: VLSI chip testing in Introduction to Algorithm