## 6.2.2 Shortest Paths between All Pairs of Nodes [4(i, j) > O]It is very often the case that the shortest paths between all pairs of nodes in a network are required. An obvious example is the preparation of tables indicating distances between all pairs of major cities and towns in road maps of states or regions, which often accompany such maps. Another example is the calculation of the distances between all pairs of "atoms" in connection with the use of the hypercube model of Section 5.4. This type of computation, as we shall see later in this chapter, is also virtually invariably required in all urban service system problems related to the location of urban facilities or to the distribution or delivery of goods. It is therefore important to have available a highly efficient method for obtaining these shortest paths. One obvious approach is the repeated application of Algorithm 6.1 of the previous section, setting each node of the graph, in succession, as the source node and thus finding the shortest-path tree associated with each and every one of the graph's nodes. Another elegant and simpleto-program approach is generally attributed to Floyd [FLOY 62]. Floyd's algorithm is simple to describe, but its logic is not particularly easy to grasp. We shall list the algorithm below, in parallel with a convenient procedure for maintaining a record of the shortest paths. This procedure was not originally a part of Floyd's algorithm-- which was only concerned with obtaining the lengths of all the shortest paths. To begin, we number the n nodes of the graph G(N, A) with the positive
integers 1, 2, . . ., n. Then, two matrices, a distance matrix,
D The algorithm then proceeds as follows: ## Shortest-Path Algorithm 2 (Algorithm 6.2)
On termination, the length, d(i, j), of the shortest path from node i to
node j is given by element d While the detailed example that follows should help clarify the algorithm for the reader, its basic rationale can be quickly illustrated. Say that the shortest path from node 4 to node 6 is the path {4, 5, 1, 7, 3, 6}. Then the first pass (k = 1) over the algorithm will replace d(5, 7) (= (5, 7)) by d(5, 1) + d(l, 7) ( = (5, 1) + (1, 7)). Then, on the third pass (k=3), d(7,6) [which may already have been changed from its original value (7, 6)] will be replaced by d(7, 3) + d(3, 6)[= (7, 3) + (3, 6)]. On the fifth pass (k = 5), the current d(4, 7) will be replaced by the sum of d(4, 5) [= (4, 5)] and d(5, 7) (with the latter as modified during pass 1). Finally, on pass seven (k = 7), d(4, 6) will be replaced by d(4, 7) + d(7, 6). This sum (from the earlier passes) is equal to (4, 5) + (5, 1) + (1, 7) + (7, 3) + (3, 6).
We wish to find the shortest paths between all pairs of nodes for the mixed
graph of figure 6.6. Since there are five nodes in the graph, five passes over the
algorithm will be required. The initial matrices D Note that on the last pass no improvements could be found for
D For another illustration, the shortest path from node 4 to node 3 is
d(4, 3) = 8 units long and the path is {4, 2, 1, 3}. The predecessor entries
that must be read are, in order, p |