Advanced High-School Mathematics

132 CHAPTER 2 Discrete Mathematics

Of course, a weighted graph can be thought of as being directed
where the weights are the same in both directions.

Dijkstra’s algorithm^36 constructs in a graphGadirected treestart-
ing from the vertex v 0 such that the minimal-weight path fromv 0 to
any other vertex v can be found by moving from v 0 to v along this
tree. The description of the algorithm proceeds as follows. We shall
assume, for convenience that all directed edges are initially drawn as
“dotted directed edges.” Also, each vertex shall initially carry a tem-
porary label, to be replaced eventually with a permanent label (which
will represent the minimal distance from the initial vertexv 0. (Caution:
the temporary labels can change during the algorithm!)

We’ll use the graph to the right
to illustrate Dijkstra’s algorithm.

k^5 -

7

1 6

2

4 8

k?

k

v 0

• k

k - k? - k?k

We now itemize the steps in Dijkstra’s algorithm.

(^36) There are a couple of really nice applets demonstrating Dijkstra’s algorithm:
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
http://www-b2.is.tokushima-u.ac.jp/ ikeda/suuri/dijkstra/Dijkstra.shtml