Posted by Jacob Eliosoff on December 14, 19100 at 03:03:41:

OK, after my failure to straighten this out in today's tutorial,

here's an explanation of Dijkstra's algorithm. See also the notes for

lecture 16.

Recall that the algorithm takes a graph G with weighted edges, and a

node A in G, and produces the minimum path length from A to each other node

in G.

The following is easier to understand with an example. I liked the

one at odin.ee.uwa.edu.au/~morris/Year2/PLDS210/dij-op.html, and

live-action demo freaks may enjoy the animation at

odin.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html.

How it works:

The algorithm builds up a set S of nodes whose optimal path lengths

have been conclusively calculated. Initially S is empty; by the time the

algorithm ends, every node in G is in S.

As we go, we keep track of the best path length seen so far for each

node. For a node N, call this d[N].

To start, set d[A] to 0 (since the shortest path from A to A is

certainly of length 0), and d[N] to infinity for all other nodes N. Then

repeatedly iterate the following loop until all nodes are in S:

1. Of the nodes which aren't yet in S, find the one, C, with the

lowest path length so far, d[C].

2. Add C to S. C's current path length d[C] has now been correctly

calculated and will no longer be decreased.

3. Now "relax" all other nodes which are adjacent to C and not yet in

S. This means, for each such node N, compute d = d[C] + edge(C, N). If

d < d[N], update: d[N] := d.

After n iterations of this loop, all the d[N]s are correct.

This algorithm is easier to remember if you can see why it works, ie,

why it's guaranteed to find the shortest path from each node to A. But to

explain that in writing would probably just be confusing. You're welcome

to ask me or Will in office hours. Meanwhile, please let me know if you

want anything here clarified, or of course if you have other questions.

-Jacob