Prev: Dynamic cycle Detection
Next: VLSI chip testing in Introduction to Algorithm
From: Le Chaud Lapin on 7 May 2007 13:25
On May 7, 9:02 am, Googmeister <googmeis...(a)gmail.com> wrote:
> 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).

Binary heap for larger networks? I do not have Sedgewick's book (or
any books). Do you have a link that shows what structure you are
referring to? I was not aware that the standard binary heap could be
made to support decrease-key. Note that I am well aware that it is
possible to make data structures that support all operations in
O[logn] time. What I am getting here is words. The words "binary
heap", at least in my mind, invokes a very particular data structure.
If there is something different that is still called a binary heap, I
would like to know what it is.

-Le Chaud Lapin-

From: Le Chaud Lapin on 7 May 2007 13:43
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.

To reiterate, that is true for binomial heaps, but not for binary
heaps. I am wondering if by "simple priority queue", the OP meant
binary heap.

> 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.

One of those implementations is a binary heap. I will not work, but
perhaps what has become the most popular online article in the world
on Dijkstra's algorithm seems to think that it can be implemented
using a binary heap:

"With a binary heap, the algorithm requires O(( | E | + | V | )log | V
| ) time (which is dominated by O( | E | log | V | ) assuming every
vertex is connected, i.e., |E| \geq |V| - 1), and the Fibonacci heap
improves this to O( | E | + | V | log | V | "

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

So as we do not getting into splitting hairs, when I read this
article, at Wikipedia, I take the phrase "binary heap" to mean the
type of heap as defined by another Wikipedia article "Binary
Heap" (http://en.wikipedia.org/wiki/Binary_heap).

The point is that, a novice reading these two articles might be left
with the impression that Dijkstra's algorithm can be implemented using
binary heaps, as defined by the articles, which is simply not true.

-Le Chaud Lapin-

From: Le Chaud Lapin on 7 May 2007 13:54
On May 7, 9:02 am, Googmeister <googmeis...(a)gmail.com> wrote:
> 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.

I would exercise caution here. The OP mentioned 50 nodes, 50 edges.

When one thinks about actually implementing the algorithm, that is
quite a bit. 50*50 = 2500, but it gets worse than that. An
associative array or list does not lend itself well to finding the
item with least cost (priority). Also, there needs to be structure to
define adjacency between nodes while updating the cost to source of
nodes.

So each relaxation step, one must:

1. Scan entire list to find node of least cost
2. Find all the nodes that are adjacent to that node
3. If adjacent node has cost greater than tentative cost, update
adjacent node cost Note that this implies linkage from a node to all
adjacent nodes. Also declare adjacent nodes pointer-back-toward-
source to be the node found during scan.
4. Remove the least-cost node from scan list.

The graph mentioned by the OP is sparsely connected, so the number of
edges is not a serious problem, but still, it's order n-squared at
least.

But this is not the real issue. The real issue is that once you go to
implement the algorithm, the simple data structures like binary heaps,
binomial heaps, etc...will start to become very hair very fast,
especially the scanning for adjacency.

-Le Chaud Lapin-

From: Le Chaud Lapin on 7 May 2007 14:30
On May 7, 12:22 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote:
> 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.

Correction: "cannot be used to implementn Dijkstra's algorithm"

> -Le Chaud Lapin-


From: Googmeister on 7 May 2007 15:57

Le Chaud Lapin wrote:
> On May 7, 9:02 am, Googmeister <googmeis...(a)gmail.com> wrote:
> > 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).
>
> Binary heap for larger networks? I do not have Sedgewick's book (or
> any books). Do you have a link that shows what structure you are
> referring to? I was not aware that the standard binary heap could be
> made to support decrease-key. Note that I am well aware that it is
> possible to make data structures that support all operations in
> O[logn] time. What I am getting here is words. The words "binary
> heap", at least in my mind, invokes a very particular data structure.
> If there is something different that is still called a binary heap, I
> would like to know what it is.

Sedgewick calls it an "index-heap-based priority queue".
It tacks on an extra array to tell you the index of element i
in the heap. It still bubbles up and bubbles down just like
a heap and uses an array to store the elements (rather than
a linked structure).

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