592
Graph Algorithms
For Exercises 7 and 8, use the directed graph that follows. Apply Dijkstra’s algorithm to the nodes given; show
the values for p and IN and the d values and s values for each pass through the while loop. Write out the nodes
in the shortest path and the distance of the path.
7. From 1 to 7
8. From 3 to 1
9. a. Modify Dijkstra’s algorithm so that it finds the shortest paths from x to all other nodes in the graph.
b. Does this change the worst-case order of magnitude of the algorithm?
10. Give an example to show that Dijkstra’s algorithm does not work when negative weights are allowed.
Another algorithm for finding shortest paths from a single source node to all other nodes in the graph is the
Bellman–Ford algorithm. In contrast to Dijkstra’s algorithm, which keeps a set of nodes whose shortest path
(minimum-weight path) of whatever length (that is, number of hops) has been determined, the Bellman–Ford
algorithm performs a series of computations that seeks to find successively smaller-weight paths of length 1,
then of length 2, then of length 3, and so on, up to a maximum of length n − 1 (if a path exists at all, then there
is a path of length no greater than n − 1). A pseudocode description of the Bellman–Ford algorithm is given
in the accompanying box; when using this algorithm, the adjacency matrix a must have a3i, i 4 = 0 for all i.
algoRitHm BEllman–ForD algorithm
Bellman–Ford(n × n matrix a; node x; array of integers d; array of nodes s)
//Computes the shortest path between a source node x and all other nodes in a simple,
//weighted, connected graph. a is a modified adjacency matrix with a3i, i 4 = 0.
//When procedure terminates, the nodes in the shortest path from x to a node y
//are y, s 3 y 4, s 3s 3 y 4 4, … , x; the distance for that path is d 3 y 4.
Local variables:
nodes z, p
//temporary nodes
array of integers t
//temporary distance array created at each iteration
//initialize arrays d and s; this establishes the shortest 1-length paths from x
d3x 4 = 0
for all nodes z not equal to x do
d 3z 4 = a3x, z 4
s 3z 4 = x
end for
//find shortest paths of length 2, 3, etc.
for i = 2 to n − 1 do
t = d
//copy current array d into array t
Graph Algorithms
For Exercises 7 and 8, use the directed graph that follows. Apply Dijkstra’s algorithm to the nodes given; show
the values for p and IN and the d values and s values for each pass through the while loop. Write out the nodes
in the shortest path and the distance of the path.
7. From 1 to 7
8. From 3 to 1
9. a. Modify Dijkstra’s algorithm so that it finds the shortest paths from x to all other nodes in the graph.
b. Does this change the worst-case order of magnitude of the algorithm?
10. Give an example to show that Dijkstra’s algorithm does not work when negative weights are allowed.
Another algorithm for finding shortest paths from a single source node to all other nodes in the graph is the
Bellman–Ford algorithm. In contrast to Dijkstra’s algorithm, which keeps a set of nodes whose shortest path
(minimum-weight path) of whatever length (that is, number of hops) has been determined, the Bellman–Ford
algorithm performs a series of computations that seeks to find successively smaller-weight paths of length 1,
then of length 2, then of length 3, and so on, up to a maximum of length n − 1 (if a path exists at all, then there
is a path of length no greater than n − 1). A pseudocode description of the Bellman–Ford algorithm is given
in the accompanying box; when using this algorithm, the adjacency matrix a must have a3i, i 4 = 0 for all i.
algoRitHm BEllman–ForD algorithm
Bellman–Ford(n × n matrix a; node x; array of integers d; array of nodes s)
//Computes the shortest path between a source node x and all other nodes in a simple,
//weighted, connected graph. a is a modified adjacency matrix with a3i, i 4 = 0.
//When procedure terminates, the nodes in the shortest path from x to a node y
//are y, s 3 y 4, s 3s 3 y 4 4, … , x; the distance for that path is d 3 y 4.
Local variables:
nodes z, p
//temporary nodes
array of integers t
//temporary distance array created at each iteration
//initialize arrays d and s; this establishes the shortest 1-length paths from x
d3x 4 = 0
for all nodes z not equal to x do
d 3z 4 = a3x, z 4
s 3z 4 = x
end for
//find shortest paths of length 2, 3, etc.
for i = 2 to n − 1 do
t = d
//copy current array d into array t