//modify t to hold shortest paths of length i
for all nodes z not equal to x do
//find the shortest path with one more link
p = node in G for which (d3 p 4 + a3 p, z 4) is minimum
t 3z 4 = d 3 p 4 + a3 p, z 4
if p ∙ z then
s 3z 4 = p
end if
end for
d = t ;
//copy array t back into d
end for
end Bellman–Ford
Section 7.3 Shortest Path and Minimal Spanning Tree
593
For Exercises 11–14 use the Bellman–Ford algorithm to find the shortest path from the source node to any other
node. Show the successive d values and s values.
11. Graph for Exercises 1–4, source node = 2 (compare your answer to Exercise 1)
12. Graph for Exercises 1–4, source node = 1 (compare your answer to Exercise 3)
13. Graph for Exercises 7–8, source node = 1 (compare your answer to Exercise 7)
14. a. Accompanying graph, source node = 1 (compare your answer to Exercise 10)
b. What does this say about the Bellman–Ford algorithm as opposed to Dijkstra’s algorithm?
To compute the distance for the shortest path between any two nodes in a graph, Dijkstra’s algorithm could be
used repeatedly, with each node in turn as the source node. A different algorithm, Floyd’s algorithm, can also
be used to solve this “all pairs” shortest-path problem, but while Floyd’s algorithm produces the weight of
all shortest paths, it does not calculate what the shortest paths actually are, that is, what nodes are on a given
shortest path. Floyd’s algorithm is very similar to Warshall’s algorithm. A description follows, where a is the
adjacency matrix of the graph with a3i, i 4 = 0 for all i.
algoRitHm FloyD’s algorithm
Floyd (n × n matrix a)
//Computes the shortest path between any two nodes in a simple, weighted,
//connected graph; a is a modified adjacency matrix with a3i,i 4 = 0.
//Upon termination, a will contain all the shortest-path distances
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
if a3i, k 4 + a3k, j 4 < a3i, j 4 then
a3i, j 4 = a3i, k 4 + a3k, j 4
end if
end for
end for
end for
end Floyd