All Pairs Shortest Paths

Given a directed, connected weighted graph G(V,E), for each edge u,vE, a weight w(u,v) is associated with the edge. The all pairs of shortest paths problem (APSP) is to find a shortest path from u to v for every pair of vertices u and v in V.

1  The representation of G

The input is an n×n matrix W=( wij ).

w(i,j)={ 0 if i=j the weight of the directed edge i,j if ij and i,jE if ij and i,jE

2  Algorithms for the APSP problem

3  Matrix Multiplication Algorithm

The algorithm is based on dynamic programming, in which each major loop will invoke an operation that is very similar to matrix multiplication. Following the DP strategy, the structure of this problem is, for any two vertices u and v,
  1. if u=v, then the shortest path p from u to v is 0.
  2. otherwise, decompose p into uxv, where p' is a path from u to x and contains at most k edges and it is the shortest path from u to x.
A recursive solution for the APSP problem is defined. Let dij (k) be the minimum weight of any path from i to j that contains at most k edges.
  1. If k=0, then

    dij (0) ={ 0 if i=j if ij

  2. Otherwise, for k1, dij (k) can be computed from dij (k-1) and the adjacency matrix w.
    dij (k) =min{ dij (k-1) , min1ln { dil (k-1) + wlj }}= min1ln { dil (k-1) + wlj }
 1     n   rows [A]
 2     C  new n×n matrix
 3    for  i   1 to  n
 4             do for  j   1 to  n
 5                            do  cij  
 6                                  for  k   1 to  n
 7                                           do  cij   min( cij , aik + bkj )
 .                                                    /* Here's where this algorithm */
 .                                                    /* differs from MATRIX-MULTIPLY. */
 8    return  C
The optimal solution can be computed by calling SPECIAL-MATRIX-MULTIPLY ( D(k) ,W) for 1kn-2. We only need to run to n-2 because that will give us D(n-1) giving us all the shortest path lengths of at most n-1 edges (you only need n-1 edges to connect n vertices). Since SPECIAL-MATRIX-MULTIPLY is called n-2 times, the total running time is O( n4 ).

3.1  The repeated squaring method

Since each D(k) matrix contains the shortest paths of at most k edges, and W really is D(1) , all we were doing in the earlier solution was going: "Given the shortests paths of at most length k, and the shortests paths of at most length 1, what is the shortests paths of at most length k+1?"
This situation is ripe for improvement. The repeated squaring method rephrases the question to: "Given the shortests paths of at most length k, what is the shortests paths of at most length k+k?" The correctness of this approach lies in the observation that the shortests paths of at most m edges is the same as the shortest paths of at most n-1 edges for all m>n-1. Thus:
D(1) =W
D(2) = W2 =W.W
D(4) = W4 = W2 . W2
D( 2log(n-1) ) = W( 2log(n-1) ) = W( 2log(n-1) -1) . W( 2log(n-1) -1)
Using repeated squaring, we only need to run SPECIAL-MATRIX-MULTIPLY log(n-1) times. Hence the running time of the improved matrix multiplication is O( n3 logn).
 1     n   rows [W]
 2     D(1)   W
 3     m   1
 4    while  m<n-1
 5                  do  D(2m)   SPECIAL-MATRIX-MULTIPLY ( D(m) , D(m) )
 6                         m   2m
 7    return  D(n)

3.2  Repeat Squaring Example

Figure 1: Example graph for the Repeated Squaring method.
Take the graph in Figure 1 for example. The weights for this graph in matrix form...

W=( 05 01 803 20 )= D(1)

Repeatedly squaring this gives us...

D(1) . D(1) =( 056 9014 51303 270 )= D(2)

D(2) . D(2) =( 0569 6014 51003 2780 )= D(4)

D(4) contains the all-pairs shortest paths. It is interesting to note that at D(2) , the shortest path from 2 to 1 is 9 using the path 2,3,1. Since the final solution ( D(4) ) allows for up to 4 edges to be used, a shorter path 2,3,4,1 was found with a weight of 6.

4  The Floyd-Warshall Algorithm

Floyd-Warshall's algorithm is based upon the observation that a path linking any two vertices u and v may have zero or more intermediate vertices. The algorithm begins by disallowing all intermediate vertices. In this case, the partial solution is simply the initial weights of the graph or infinity if there is no edge.
The algorithm proceeds by allowing an additional intermediate vertex at each step. For each introduction of a new intermediate vertex x, the shortest path between any pair of vertices u and v, x,u,vV, is the minimum of the previous best estimate of δ(u,v), or the combination of the paths from ux and xv.


Let the directed graph be represented by a weighted matrix W.
 1     n   rows [W]
 2     D(0)   W
 3    for  k   1 to  n
 4             do for  i   1 to  n
 5                            do for  j   1 to  n
 6                                           do  dij (k)   MIN ( dij (k-1) , dik (k-1) + dkj (k-1) )
 7    return  D(n)
The time complexity of the algorithm above is O( n3 ).

4.1  Floyd-Warshall Example

Figure 2: Example graph for FLOYD-WARSHALL.
Let us now work through the steps of the FLOYD-WARSHALL algorithm when it is applyed on the graph depicted in Figure 2.

W=( 018 0 2 0 30 )

  1. Allowable intermediate vertices {}: D(0) =W
  2. Allowable intermediate vertices {1}: D(1) no change
  3. Allowable intermediate vertices {1,2}:

    D(2) =( 018 3 02 0 30 )

    Where 3= min {,1+2}, using paths 12 and 24.
  4. Allowable intermediate vertices {1,2,3}: D(3) no change
  5. Allowable intermediate vertices {1,2,3,4}:

    D(4) =( 01 6 3 0 5 2 0 30 )

    Where 6= min {8,3+3}, using paths 14 and 43.
    Where 5= min {,2+3}, using paths 24 and 43.

5  The transitive closure of a directed graph

The transitive closure of a directed graph G=(V,E) tells us if there is a path from i to j, for each pair of vertices i,jV. It is itself another graph G* =(V, E* ) where E* ={i,j: there is a path from i to j in G }. The transitive closure of a directed graph G can be determined by the following algorithm.
 1     n   |V|
 2    for  i   1 to  n
 3             do for  j   1 to  n
 4                            do if  i=j or (i,j)E
 5                                        then  tij (0)   1
 6                                        else   tij (0)   0
 7    for  k   1 to  n
 8             do for  i   1 to  n
 9                            do for  j   1 to  n
 10                                           do  tij (k)   tij (k-1) ( tik (k-1) tkj (k-1) )
 11    return  T(n)

5.1  Transitive Closure Example

Figure 3: Example graph for Transitive Closure.
The matrices below illustrate the state of the TRANSITIVE-CLOSURE algorithm as it operates on the graph depicted in Figure 3.

T(0) =( 1101 0110 0011 0101 ) T(1) =( 1101 0110 0011 0101 ) T(2) =( 1111 0110 0011 0111 ) T(3) =( 1111 0111 0011 0111 ) T(4) =( 1111 0111 0111 0111 )

File translated from TEX by TTM, version 3.67.
On 31 Mar 2006, 18:12.