Dijkstra's algorithm: (Dijkstra's algorithm is found
on page 658 of your text, with additional definitions
on pages 648 and 649.).
This algorithm starts with a
single source vertex s in a weighted directed graph G,
with non-negative weights.
For each vertex v in the graph, the algorithm computes the shortest
distance from s to v.
Each vertex in v in G has two attributes:
v.d, the shortest path estimate, which is an
upper bound on the length (or weight) of the shortest path
from s to v (eventually this is the length of the
shortest path), and
v.pi, the predecessor vertex that we've seen before, creating
a spanning tree that gives the actual shortest paths.
Initializing the Graph:
This uses a function Initialize-Single-Source given in
the image below:
The Relax Step: Here w is a weight function, and
u and v are vertices, so that w(u,v)
gives the weight attached to the directed edge from u to v.
"The process of relaxing an edge (u,v) consists of testing
whether we can improve the shortest path to v found so far
by going through u and, if so, updating u.d and
u.pi."
The Algorithm Itself and an Example: Prior to the algorithm,
all vertices are inserted into a min-priority queue Q, using the
minimum value of d as the basis for removing from the queue.
In the diagram below, vertices removed from the queue are
colored black and no longer affect the algorithm. In each
case the next vertex chosen for removal is colored gray.
(The gray doesn't show up in my picture, so note which vertex is gray
in each picture: (a): s, (b): y, (c): z,
(d): t, (e): x, (f): none). The queue
keeps track of everything. The colors are not mentioned
and even the set S is only present for clarity and need
not be implemented.
More about the queue:
Beware! The d fields change from step to step
during execution, so the queue will need to use the latest d
values to return the proper vertex. Instead of trying to implement
a min-priority queue from scratch or trying to use a library
queue (both of which are difficult), you should just search through
the list of vertices for the one with current smallest d value
that has not yet been removed. This is very easy to do, although
it is not efficient. You need to keep track of which vertices
have been removed. (You could use an extra field (color
black or white) on each vertex to keep track of those
vertices not yet processed (color = white).)
Discussion: "Because Dijkstra's algorithm always chooses
the 'closest' vertex not yet picked, we say it uses a greedy
strategy", which in this case is optimal.
Revision date:2012-11-12.
(Please use ISO 8601,
the International Standard Date and Time Notation.)
