## 3.2 Floyd's Algorithm for Shortest Paths A common problem encountered by air travelers is the determination of the shortest way to fly from one city to another when a direct flight does not exist. Next we develop an algorithm that solves this and similar problems. First, let's informally review some graph theory. [Figure 3.2](#ch03fig02) shows a weighted, directed graph. Recall that in a pictorial representation of a graph the circle represent ***vertices***, and a line from one circle to another represents an ***edge*** (also called an *arc*). If each edge has a direction associated with it, the graph is called a *directed graph* or ***digraph***. When drawing an edge in such a graph, we use an arrow to show the direction. In a digraph there can be two edges between two vertices, one going in each direction. For example, in [Figure 3.2](#ch03fig02) there is an edge from *v*1 to *v*2 and an edge from *v*2 to *v*1. If the edges have values associated with them, the values are called ***weights*** and the graph is called a ***weighted graph***. We assume here that these weights are nonnegative. Although the values are ordinarily called weights, in many applications they represent distances. Therefore, we talk of a path from one vertex to another. In a directed graph, a ***path*** is a sequence of vertices such that there is an edge from each vertex to its successor. For example, in [Figure 3.2](#ch03fig02) the sequence \[*v*1, *v*4, *v*3\] is a path because there is an edge from *v*1 to *v*4 and an edge from *v*4 to *v*3. The sequence \[*v*3, *v*4, *v*1\] is not a path because there is no edge from *v*4 to *v*1. A path from a vertex to itself is called a ***cycle***. The path \[*v*1, *v*4, *v*5, *v*1\] in [Figure 3.2](#ch03fig02) is a cycle. If a graph contains a cycle, it is ***cyclic***; otherwise, it is a ***cyclic***. A path is called ***simple*** if it never passes through the same vertex twice. The path \[*v*1, *v*2, *v*3\] in [Figure 3.2](#ch03fig02) is simple, but the path \[*v*1, *v*4, *v*5, *v*1, *v*2\] is not simple. Notice that a simple path never contains a subpath that is a cycle. The ***length*** of a path in a weighted graph is the sum of the weights on the path; in an unweighted graph it is simply the number of edges in the path. [](fig3-2_0.jpg) Figure 3.2: A weighted, directed graph. A problem that has many applications is finding the shortest paths from each vertex to all other vertices. Clearly, a shortest path must be a simple path. In [Figure 3.2](#ch03fig02) there are three simple paths from *v*1 to *v*3—namely \[*v*1, *v*2, *v*3\] \[*v*1, *v*4, *v*3\] and \[*v*1, *v*2, *v*4, *v*3\]. Because  \[*v*1, *v*4, *v*3\] is the shortest path from *v*1 to *v*3. As mentioned previously, one common application of shortest paths is determining the shortest routes between cities. The Shortest Paths problem is an ***optimization problem***. There can be more than one candidate solution to an instance of an optimization problem. Each candidate solution has a value associated with it, and a solution to the instance is nay candidate solution that has an optimal value. Depending on the problem, the optimal value is either the minimum or the maximum. In the case of the Shortest Paths problem, a *candidate solution* is a path from one vertex to another, the *value* is the length of the path, and the *optimal value* is the minimum of these lengths. Because there can be more than one shortest path from one vertex to another, our problems to find any one of the shortest paths. An obvious algorithm for this problem would be to determine, for each vertex, the lengths of all the paths from that vertex to each other vertex, and to compute the minimum of these lengths. However, this algorithm is worse than exponential-time. For example, suppose there is an edge from every vertex to every other vertex. Then a subset of all the paths from one vertex to another vertex is the set of the all those paths that start at the first vertex, end at the other vertex, and pass through all the other vertices. Because the second vertex on such a path can be any of *n* − 2 vertices, the third vertex on such a path can be any of *n* − 3 vertices, …, and the second-to-last vertex on such a path can be only one vertex, the total number of paths from one vertex to another vertex that pass through all the other vertices is  which is worse than exponential. We encounter this same situation in many optimization problems. That is, the obvious algorithm that considers all possibilities is exponential-time or worse. Our goal is to find a more efficient algorithm. Using dynamic programming, we create a cubic-time algorithm for the Shortest Paths problem. First we develop an algorithm that determines only the lengths of the shortest paths. After that we modify it to produce shortest paths as well. We represent a weighted graph containing *n* vertices by an array *W* where  Because vertex *v*j is said to be ***adjacent*** to *v**i* if there is an edge from *v**i* to *v**j*, this array is called the ***adjacency matrix*** representation of the graph. The graph in [Figure 3.2](#ch03fig02) is represented in this manner in [Figure 3.3](#ch03fig03). The array *D* in [Figure 3.3](#ch03fig03) contains the lengths of the shortest paths in the graph. For example, *D*\[3\] \[5\] is 7 because 7 is the length of a shortest path from *v*3 to *v*5. If we can develop a way to calculate the values in *D* from those in *W*, we will have an algorithm for the Shortest Path problem. We accomplish this by creating a sequence of *n* + 1 arrays *D*(*k*), where 0 ≤ *k* ≤ *n* and where  [](fig3-3_0.jpg) Figure 3.3: *W* represents the graph in [Figure 3.2](#ch03fig02) and *D* contains the lengths of the shortest paths. Our algorithm for the Shortest Paths problem computes the values in *D* from those in *W*. Before showing why this enables us to compute *D* from *W*, let's illustrate the meaning of the items in these arrays. Example 3.2****We will calculate some exemplary values of *D**k* \[*i*\]\[*j*\] for the graph in [Figure 3.2](#ch03fig02)  The last value computed, *D*(5) \[2\] \[5\], is the length of a shortest path from v2 to v5 that is allowed to pass through any of the other vertices. This means that it is the length of a shortest path. **** Because *D*(*n*) \[*i*\[*j*\] is the length of a shortest path from *v**i* to *v* *j* that is allowed to pass through any of the other vertices, it is the length of a shortest path from *v*i to *v*j. Because *D*(0) \[*i*\]\[*j*\] is the length of a shortest path that is not allowed to pass through any other vertices, it is the weight on the edge from *v*1 to *v**j*. We have established that  Therefore, to determine *D* from *W* we need only find a way to obtain *D*(n) from *D*(0). The steps for using dynamic programming to accomplish this are as follows: 1. *Establish* a recursive property (process) with which we can compute *D*(k) from *D*(*k*−1). 2. Solve an instance of the problem in a *bottom-up* fashion by repeating the process (established in Step 1) for *k* = 1 to *n*. This creates the sequence  We accomplish Step 1 by considering two cases: **Case 1.** At least one shortest path from *v**i* to *v**j*, using only vertices in {*v*1, *v*2…, *v**k*} as intermediate vertices, does not use *v**k*. Then  An example of this case in [Figure 3.2](#ch03fig02) is that  because when we include vertex *v*5, the shortest path from *v*1 to *v*3 is still \[*v*1, *v*4, *v*3\]. **Case 2**. All shortest paths from *v*1 to *v**j*, using only vertices in {*v*1, *v*2, …, *v**k*} as intermediate vertices, do use *v**k*. In this case any shortest path appears as in [Figure 3.4](#ch03fig04). Because *v**k* cannot be an intermediate vertex on the subpath from *v**i* to *v**k*, that subpath uses only vertices in {*v*1, *v*2...., *v**k−1*} as intermediates. This implies that the subpath's length must be equal to *D**k*−1 \[*i*\] \[*k*\] for the following reasons: First, the subpath's length cannot be shorter because *D**k*−1) \[*i*\] \[*k*\] is the length of a shortest path from *v*1 it *v*k using only vertices in {*v*1, *v*2, …, *v**k*−1} as intermediates. Second, the subpath's length cannot be longer because if it were, we could replace it in [Figure 3.4](#ch03fig04) by a shortest path, which contradicts that fact that the entire path in [Figure 3.4](#ch03fig04) is a shortest path. Similarly, the length of the subpath from *v* *k* to *v**j* in [Figure 3.4](#ch03fig04) must be equal to *D**k*-1) \[*k*\] \[*j*\]. Therefore, in the second case [](fig3-4_0.jpg) Figure 3.4: The shortest path uses vk  An example of the second case in [Figure 3.2](#ch03fig02) is that  Because we must have either Case 1 or Case 2, the value of *D*(*k*\[*i*\] \[*j*\] is the minimum of the values on the right in Equalities 3.3 and 3.4. This means that we can determine *D*(*k*) from *D*(*k*−1) as follows:  We have accomplished Step 1 in the development of a dynamic programming algorithm. To accomplish Step 2, we use the recursive property in Step 1 to create the sequence of arrays shown in Expression 3.2. Let's do an example showing how each of these arrays is computed from the various one. Example 3.3****Given the graph in [Figure 3.2](#ch03fig02), which is represented by the adjacency matrix *W* in [Figure 3.3](#ch03fig03), some sample computations are as follows (recall that *D*(0) = *W*):  Once the whole array *D*(1) is computed, the array *D*(2) is computed. A sample computation is  After computing all of *D*(2), we continue in sequence until *D*(5) is computed. This final array is *D*, the lengths of the shortest paths. It appears on teh right in [Figure 3.3](#ch03fig03). **** Next we present the algorithm developed by Floyd (1962) and known as *Floyd's algorithm*. Following the algorithm, we explain why it uses only one array *D* besides the input array *W*. Algorithm 3.3: Floyd's Algorithm for Shortest Paths****Problem: Compute the shortest paths from each vertex in a weighted graph to each of the other vertices. The weights are nonnegative numbers. Inputs: A weighted, directed graph and *n*, the number of vertices in the graph. The graph is represented by a two-dimensional array *W* which has both its rows and columns indexed from 1 to *n*, where *W*\[*i*\]\[*j*\] is the weight on the edge from the *i*th vertex to the *j*th vertex. Outputs: A two-dimensional array *D*, which has both its rows and columns indexed from 1 to *n*, where *D*\[*i*\] \[*j*\] is the length of a shortest path from the *i*th vertex to the *j*th vertex. ``` void floyd (int n const number W[] [] number D[] [] { index i, j, k; D = W; for (k = 1; k<=n; k++) for (i = 1; i <= n; i++) for (i = 1; j <= n; j++) D[i][j] = minimum(D[i][j], D[i][k] + D[k][j]); } ``` **** We can perform our calculations using only one array *D* because the values in the *k*th row and the *k*th column are not changed during the *k*th iteration of the loop. That is, in the *k*th iteration the algorithm assigns.  which clearly equals *D*\[*i*\]\[*k*\], and  which clearly equals *D* \[*k*\] \[*j*\]. During the *k*th iteration, *D* \[*i*\] \[*j*\] is computed from only its own value and values in the *k*th row and the *k*th column. Because these values have maintained their values from the (*k* − 1)st iteration, they are the values we want. As mentioned before, sometimes after developing a dynamic programming algorithm, it is possible to revise the algorithm to make it more efficient in terms of space. Next we analyze Floyd's Algorithm. ****Analysis of Algorithm 3.3 Every-Case Time Complexity (Floyd's Algorithm for Shortest Paths)Basic operation: The instruction in the for-*j* loop. Input size: *n*, the number of vertices in the graph. We have a loop within a loop within a loop, with *n* passes through each loop. So.  **** The following modification to Algorithm produces shortest paths. Algorithm 3.4: Floyd's Algorithm for Shortest Paths 2****Problem: same as in [Algorithm 3.3](#ch03ex06), except shortest paths are also created. Additional outputs: an array *P*, which has both its rows and columns indexed from 1 to *n*, where  ``` void floyd2 (int n, const number W[] [], number D[] [], index P[] []) { index, i, j, k; for(i = 1; i <= n; i++) for (j = 1; j <= n; j++) P[i] [j = 0; D = W for (k = 1; k <= n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if (D[i][k] + D[k][j] < D[i][j]){ P[i][j] = k; D[i][j[ = D[i[[k] + D[k][j]; } } ``` **** [Figure 3.5](#ch03fig05) shows the array *P* that is created when the algorithm is applied to the graph in [Figure 3.2](#ch03fig02). [](fig3-5_0.jpg) Figure 3.5: The array *P* produced when [Algorithm 3.4](#ch03ex07) is applied to the graph in [Figure 3.2](#ch03fig02). The following algorithm produces a shortest path from vertex *v**q* to *v**e* using the array *P*. Algorithm 3.5: Print Shortest Path****Problem: Print the intermediate vertices on a shortest path from one vertex to another vertex in a weighted graph. Inputs: the array *P* produced by [Algorithm 3.4](#ch03ex07), and two indices, *q* and *r*, of vertices in the graph that is the input to [Algorithm 3.4](#ch03ex07).  Outputs: the intermediate vertices on a shortest path from *v**q* to *v**r*. ``` void path (index q, r) { if (P[ q ] [ r ] ! = 0) { path (q, P[q] [r]); cout < < "v" < < P[ q ] [ r ]; path (P[ q ] [ r ], r); } } ``` **** Recall the convention established in [Chapter 2](LiB0014.html#141) of making only variables. whose values can change in the recursive calls, inputs to recursive routines. Therefore, the array *P* is not an input to *path.* If the algorithm were implemented by defining *p* globally, and we wanted a shortest path from *v**q* to *v**r*, the top-level call to *path* would be as follows: ``` path (q, r); ``` Given the value of *P* in [Figure 3.5](#ch03fig05), if the values of *q* and *r* were 5 and 3, respectively, the output would be  These are the intermediate vertices on a shortest path from *v*5 to *v*3. In the exercises we establish that *W* (*n* ∊) Θ(*n*) for [Algorithm 3.5](#ch03ex08)