582
Graph Algorithms
and nodes x and y; the algorithm writes out the shortest path between x and y and
the distance for that path. Here shortest path means minimum-weight path. We
actually assume a modified adjacency matrix a, where a3i, j 4 is the weight of the
arc between i and j if one exists and a3i, j 4 has the value ∞ if no arc exists (here
the symbol ∞ denotes a number larger than any weight in the graph).
algoRitHm Dijkstra’s algorithm
Dijkstra (n × n matrix a; nodes x, y)
//Computes the shortest path between a source node x and a destination node y
//in a simple, connected graph with positive weights. a is a modified adjacency
//matrix. Writes out nodes in the shortest path from x to y, and the
//distance for that path.
Local variables:
set of nodes IN
//set of nodes whose shortest path from x is known
nodes z, p
//temporary nodes
array of integers d
//for each node, the distance from x using nodes in IN
array of nodes s
//for each node, the previous node in the shortest path
integer OldDistance
// distance to compare against
//initialize set IN and arrays d and s
IN = 5x6
d 3x 4 = 0
for all nodes z not in IN do
d 3z 4 = a3x, z 4
s 3z 4 = x
end for
//process nodes into IN
while y not in IN do
//add minimum-distance node not in IN
p = node z not in IN with minimum d 3z 4
IN = IN c 5 p6
//recompute d for non IN nodes, adjust s if necessary
for all nodes z not in IN do
OldDistance = d 3z 4
d 3z 4 = min(d 3z 4, d 3 p 4 + a3 p, z 4)
if d3z 4 ∙ OldDistance then
s 3z 4 = p
end if
end for
end while