This section presents two algorithms for solving both cyclic (i.e., containing loops) and acyclic networks:
1. Dijkstra's algorithm
2. Floyd's algorithm
Dijkstra's algorithm is designed to determine the shortest routes between the source node and every other node in the network. Floyd's algorithm is more general because it allows the determination of the shortest route between any two nodes in the network.
Dijkstra's Algorithm. Let ui be the shortest distance from source node 1 to node i, and define dij (≥0) as the length of arc (i, j). Then the algorithm defines the label for an immediately succeeding node j as
The label for the starting node is [0, --], indicating that the node has no predecessor. Node labels in Dijkstra's algorithm are of two types: temporary and permanent. A temporary label is modified if a shorter route to a node can be found. If no better route can be found, the status of the temporary label is changed to permanent.
The network in Figure 6.15 gives the permissible routes and their lengths in miles between city 1 (node 1) and four other cities (nodes 2 to 5). Determine the shortest routes between city 1 and each of the remaining four cities.
Iteration 0. Assign the permanent label [0, -- ] to node 1.
Iteration 1. Nodes 2 and 3 can be reached from (the last permanently labeled) node 1. Thus, the list of labeled nodes (temporary and permanent) becomes
For the two temporary labels [100, 1] and [30, 1], node 3 yields the smaller distance (u3 = 30). Thus, the status of node 3 is changed to permanent.
Iteration 2. Nodes 4 and 5 can be reached from node 3, and the list of labeled nodes becomes
The status of the temporary label [40,3] at node 4 is changed to permanent (u4 = 40).
Iteration 3. Nodes 2 and 5 can be reached from node 4. Thus, the list of labeled nodes is updated as
Node 2's temporary label [100, 1] obtained in iteration 1 is changed to [55,4) in iteration 3 to indicate that a shorter route has been found through node 4. Also, in iteration 3, node 5 has two alternative labels with the same distance u5 = 90.
The list for iteration 3 shows that the label for node 2 is now permanent.
Iteration 4. Only node 3 can be reached from node 2. However, node 3 has a permanent label and cannot be relabeled. The new list of labels remains the same as in iteration 3 except that the label at node 2 is now permanent. This leaves node 5 as the only temporary labeL Because node 5 does not lead to other nodes, its status is convert-ed to permanent, and the process ends.
The computations of the algorithm can be carried out more easily on the network, as Figure 6.16 demonstrates.
The shortest route between nodes 1 and any other node in the network is determined by starting at the desired destination node and backtracking through the nodes using the information given by the permanent labels. For example, the following sequence determines the shortest route from node 1 to node 2:
(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30,1] -> (1)
Thus, the desired route is 1 -> 3 -> 4 -> 2 with a total length of 55 miles.
1. The network in Figure 6.17 gives the distances in miles between pairs of cities 1,2, ., . , and 8. Use Dijkstra's algorithm to find the shortest route between the following cities:
a. Cities 1 and 8
b. Cities 1 and 6
c. Cities 4 and 8
d. Cities 2 and 6
2. Use Dijkstra's algorithm to find the shortest route between node 1 and every other node in the network of Figure 6.18.
3. Use Dijkstr'a algorithm to determine the optimal solution of each of the following problems:
a. Problem 1, Set 6.3a.
b. Problem 2, Set 6.3a.
c. Problem 4, Set 6.3a.
Floyd's Algorithm. Floyd's algorithm is more general than Dijkstra's because it determines the shortest route between any two nodes in the network. The algorithm represents an n-node network as a square matrix with n rows and n columns. Entry (~j) of the matrix gives the distance dij from node i to node j, which is finite if i is linked directly to j, and infinite otherwise.
The idea of Floyd's algorithm is straightforward. Given three nodes i j, and k in Figure 6.19 with the connecting distances shown on the three arcs, it is shorter to reach j from i passing through k if
In this case, it is optimal to replace the direct route from i -> j with the indirect route i -> k -> j. This triple operation exchange is applied systematically to the network using the following steps:
Step 0. Define the starting distance matrix Do and node sequence matrix So as given below. The diagonal elements are marked with (--) to indicate that they are blocked. Set k = 1.
General step k. Define row k and column k as pivot row and pivot column. Apply the triple operation to each element d jj in Dk - l , for all i and j. If the condition
is satisfied, make the following changes:
a) Create Dk by replacing dij in Dk - 1 with djk + dkj
b) Create Sk by replacing Sij in Sk-l with k. Set k = k + 1. If k = n + 1, stop; else repeat step k.
Step k of the algorithm can be explained by representing Dk - 1 as shown in Figure 6.20. Here, row k and column k define the current pivot row and column. Row i
represents any of the rows 1, 2, ... , and k - 1, and row p represents any of the rows k + 1, k + 2, ... , and n. Similarly, column j represents any of the columns 1,2, ... , and k - 1, and column q represents any of the columns k + 1, k + 2, ... , and n. The triple operation can be applied as follows. If the sum of the elements on the pivot row and the pivot column (shown by squares) is smaller than the associated intersection element (shown by a circle), then it is optimal to replace the intersection distance by the sum of the pivot distances.
After n steps, we can determine the shortest route between nodes i and j from the matrices Dn and Sn using the following rules:
a) From Dm dij gives the shortest distance between nodes i and j.
b) From Sm determine the intermediate node k = sij that yields the route i -> k -> j. If sik = k and skj = j, stop; all the intermediate nodes of the route have been found. Otherwise, repeat the procedure between nodes i and k, and between nodes k and j.
For the network in Figure 6.21, find the shortest routes between every two nodes. TIle distances (in miles) are given on the arcs. Arc (3,5) is directional, so that no traffic is allowed from node 5 to node 3. All the other arcs allow two-way traffic.
Iteration 0. The matrices Do and So give the initial representation of the network. Do is sym-metrical, except that d33 = ¥ because no traffic is allowed from node 5 to node 3.
Set k = 1. The pivot row and column are shown by the lightly shaded first row and first column in the Do-matrix. The darker cells, d13 and d 32 , are the only ones that can be improved by the triple operation. Thus, D1 and SI are obtained from Do and So in the following manner:
Set k = 2, as shown by the lightly shaded row and column in D1• The tripLe oper-ation is applied to the darker cells in D1 and S1. The resulting changes are shown in bold in D2 and S2.
Set k = 3, as shown by the shaded row and column in D2. The new matrices are given by D3 and S3.
Iteration 4. Set k = 4, as shown by the shaded row and column in D3. The new matrices are given by D4 and S4.
Iteration 5. Set k = 5, as shown by the shaded row and column in D4. No further improvements are possible in this iteration.
The final matrices D4 and S4 contain all the information needed to determine the shortest route between any two nodes in the network. For example, from D4, the shortest distance from node 1 to node 5 is d l5 = 12 miles. To determine the associated route, recall that a segment (i, j) represents a direct link only if sij = j. Otherwise, i and j are linked through at least one other intermediate node. Because sij = 4 != 5, the route is initially given as 1 -> 4 -> 5. Now, because s14 = 2 != 4, the segment'(I,4) is not a direct link, and 1 -> 4 is replaced with 1 -> 2 -> 4, and the route 1 -> 4 -> 5 now becomes 1 -> 2 -> 4 -> 5. Next, because s12 = 2, s24 = 4, and s45 = 5, no further "dissecting" is needed, and 1 -> 2 -> 4 -> 5 defines the shortest route.
PROBLEM SET 6.3C
1. In Example 6.3-5, use Floyd's algorithm to determine the shortest routes between each of the following pairs of nodes:
*(a) From node 5 to node 1.
(b) From node 3 to node 5.
(c) From node 5 to node 3.
(d) From node 5 to node 2.
2. Apply Floyd's algorithm to the network in Figure 6.22. Arcs (7,6) and (6,4) are unidirectional, and all the distances are in miles. Determine the shortest route between the following pairs of nodes:
(a) From node 1 to node 7.
(b) From node 7 to node 1.
(c) From node 6 to node 7.
3. The Tell-All mobile-phone company services six geographical areas. The satellite distances (in miles) among the six areas are given in Figure 6.23. Tell-All needs to determine the most efficient message routes that should be established between each two areas in the network.
*4. Six kids, Joe, Kay, Jim, Bob, Rae, and Kim, playa variation of hide and seek. The hiding place of a child is known only to a select few of the other children. A child is then paired with another with the objective of finding the partner's hiding place. This may be achieved through a chain of other kids who eventually will lead to discovering where the designated child is hiding. For example, suppose that Joe needs to find Kim and that Joe knows where Jim is hiding, who in turn knows where Kim is. Thus, Joe can find Kim by first finding Jim, who in turn will lead Joe to Kim. The following list provides the where-abouts of the children:
Joe knows the hiding places of Bob and Kim.
Kay knows the hiding places of Bob, Jim, and Rae.
Jim and Bob each know the hiding place of Kay only.
Rae knows where Kim is hiding.
Kim knows where Joe and Bob are hiding.
Devise a plan for each child to find every other child through the smallest number of contacts. What is the largest number of contacts?