Prev: Dynamic cycle Detection
Next: VLSI chip testing in Introduction to Algorithm
From: Googmeister on 7 May 2007 16:01

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

Yes, 50*50 = 2500, but how is this relevant? You still store
the graph using a sparse representation and run Dijkstra's
algorithm. But for the priority queue, use one array (of size
equal to the number of nodes) where the ith element in
the array stores the priority of node i.

> An
> associative array or list does not lend itself well to finding the
> item with least cost (priority).

The point is that it doesn't make much difference if
there are only 50 element to scan.

From: wade on 7 May 2007 16:28
On May 7, 12:43 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote:

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

You are correct in the sense that the wiki article on binary heaps
doesn't tell you how to implement "increase priority" in logN time.

However, a binary heap does support that operation. Its
implementation is the same as described under wikipedia's binomial
heap. After increasing a node's priority, while its priority is
greater than its parent's, swap it with its parent.

From: Ben Pfaff on 7 May 2007 16:21
Le Chaud Lapin <jaibuduvin(a)gmail.com> writes:

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

I think that we might be talking about a data structure like the
one that I implemented here:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/heap.h?rev=1.1&root=pspp&view=auto
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/heap.c?rev=1.1&root=pspp&view=auto
I didn't get the idea from Sedgewick, though.
--
Ben Pfaff
http://benpfaff.org
From: Mitch on 7 May 2007 17:15
On May 7, 1:25 pm, Le Chaud Lapin <jaibudu...(a)gmail.com> wrote:

> I was not aware that the standard binary heap could be
> made to support decrease-key.

while (key of node is greater than parent's) {
swap keys of n and and parent
node = parent of node
}

see Cormen Leiserson Rivest Stein,p 140 Heap-Increase-Key

Mitch

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