7.2.3 All Pairs Shortest Paths Problem: Floyd's Algorithm

REF.

Robert W Floyd. Algorithm 97 (Shortest Path). Communications of the ACM, Volume 5, Number 6, pp. 345, 1962.

$$: \mbox{A digraph $G = (V, E)$\space in which eacharc $v \rightarrow w$\space has}$$ tex2html_deferredGiven

$$\mbox{a nonnegative cost $C[v,w]$ }$$

$$\mbox{{\bf To find}} : \mbox{For each ordered pair of vertices $(v,w)$ , thesmallest}$$

$$\mbox{ length of any path from $v$\space to $w$ }$$

Floyd's Algorithm

• This is an O(n³) algorithm, where n is the number of vertices in the digraph.
• Uses the principle of Dynamic Programming
• Let V = {1, 2,..., n}. The algorithm uses a matrix A[1..n][1..n] to compute the lengths of the shortest paths.
• Initially,

$$\neq$$ A[i, j] = (7.12)

= 0          if  i = j

Note that C[i, j] is taken as $\infty$ if there is no directed arc from ito j.

• The algorithm makes n passes over A. Let A₀, A₁,..., A_nbe the values of A on the n passes, with A₀ being the initial value. Just after the k-1^th iteration,

$$\mbox{Smallestlength of any path from vertex $i$\space to vertex $j$ }$$ A_{k - 1}[i, j] = (7.13)

$$\mbox{ that doesnot pass through the vertices $k, k+1, \ldots, n$ }$$ (7.14)

$$\mbox{(i.e. thatonly passes through possibly 1, 2, . . . $k-1$ )}$$


See Figure 7.8

• The k^th pass explores whether the vertex k lies on an optimal path from i to j, $\forall$ i, j

 

 

Figure 7.8: Principle of Floyd's algorithm


• We use 
A_k[i, j] = min$$\left\{\vphantom{\begin{array}{l} A_{k-1} [i,j] \\ A_{k-1}[i,k] +A_{k-1}[k,j]\end{array} }\right.$$$$\begin{array}{l} A_{k-1} [i,j] \\ A_{k-1}[i,k] +A_{k-1}[k,j]\end{array}$$$$\left.\vphantom{\begin{array}{l} A_{k-1} [i,j] \\ A_{k-1}[i,k] +A_{k-1}[k,j]\end{array} }\right.$$
• The algorithm:


void Floyd (floatC[n - 1][n - 1], A[n - 1][n - 1])

        { int i, j, k;

                { for(i = 0, i$\leq$n - 1;i + +)

                    for(j = 0;j$\leq$n - 1, j + +)

                        A[i, j] = C[i, j];

                    for(i = 0;i$\leq$n - 1;i + +)

                        A[i, i] = 0;

                            for(k = 0;k$\leq$n - 1;k + +);

                                 {

                                    for(i = 0;i$\leq$n - 1;i + +)

                                          {

                                                for(j = 0;j$\leq$n - 1, j + +)

                                                    if(A[i, k] + A[k, j] < A[i, j])

                                                    A[i, j] = A[i, k] + A[k, j]

                                    }

                            }

                       }

}

Figure 7.9: A digraph example for Floyd's algorithm

Example: See Figure 7.9.

C = $$\left[\vphantom{\begin{array}{ccc} 2 & 8 & 5 \\ 3 & \infty& \infty\\ \infty& 2 & \infty\\ \end{array} }\right.$$$$\begin{array}{ccc} 2 & 8 & 5 \\ 3 & \infty& \infty\\ \infty& 2 & \infty\\ \end{array}$$$$\left.\vphantom{\begin{array}{ccc} 2 & 8 & 5 \\ 3 & \infty& \infty\\ \infty& 2 & \infty\\ \end{array} }\right]$$

$$\left[\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & \infty\\ \infty& 2 &0 \\ \end{array} }\right. \begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & \infty\\ \infty& 2 &0 \\ \end{array} \left.\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & \infty\\ \infty& 2 &0 \\ \end{array} }\right] \left[\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 &0 & 8 \\ \infty& 2 & 0 \\ \end{array} }\right. \begin{array}{ccc} 0 & 8 & 5 \\ 3 &0 & 8 \\ \infty& 2 & 0 \\ \end{array} \left.\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 &0 & 8 \\ \infty& 2 & 0 \\ \end{array} }\right]$$ A₀ = (7.15)

$$\left[\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array}}\right. \begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array} \left.\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array}}\right] \left[\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array}}\right. \begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array} \left.\vphantom{\begin{array}{ccc} 0 & 8 & 5 \\ 3 & 0 & 8 \\ 5 & 2 & 0 \\ \end{array}}\right]$$ A₂ =

• With adjacency matrix representation, Floyd's algorithm has a worst case complexity of O(n³) where n is the number of vertices
• If Dijkstra's algorithm is used for the same purpose, then with an adjacency list representation, the worst case complexity will be O(nelog n). Thus if e is O(n²), then the complexity will be O(n³log n) while if e is O(n), then the complexity is O(n²log n).