Dijkstra's algorithm


[ Follow Ups ] [ Post Followup ] [ WWWBoard for 308-203A ] [ FAQ ]

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



Follow Ups:



Post a Followup

Name:
E-Mail:

Subject:

Comments:

Optional Link URL:
Link Title:
Optional Image URL:


[ Follow Ups ] [ Post Followup ] [ WWWBoard for 308-203A ] [ FAQ ]