Graph

    \\begin{pmatrix}
    0 & 5 & \\infty & 2 & \\infty \\\\
    \\infty & 0 & 2 & \\infty & \\infty \\\\
    3 & \\infty & 0 & \\infty & 7 \\\\
    \\infty & \\infty & 4 & 0 & 1 \\\\
    1 & 3 & \\infty & \\infty & 0 \\\\
    \\end{pmatrix}
Graph and matrix of lengths

Floyd-Warshall algorithm is a procedure, which is used to find the shorthest (longest) paths among all pairs of nodes in a graph, which does not contain any cycles of negative lenght. The main advantage of Floyd-Warshall algorithm is its simplicity.

Description

Floyd-Warshall algorithm uses a matrix of lengths D_{0} as its input. If there is an edge between nodes i and j, than the matrix D_{0} contains its length at the corresponding coordinates. The diagonal of the matrix contains only zeros. If there is no edge between edges i and j, than the position (i,\\;j) contains positive infinity. In other words, the matrix represents lengths of all paths between nodes that does not contain any intermediate node.

In each iteration of Floyd-Warshall algorithm is this matrix recalculated, so it contains lengths of paths among all pairs of nodes using gradually enlarging set of intermediate nodes. The matrix D_{1}, which is created by the first iteration of the procedure, contains paths among all nodes using exactly one (predefined) intermediate node. D_{2} contains lengths using two predefined intermediate nodes. Finally the matrix D_{n} uses n intermediate nodes.

This transformation can be described using the following recurrent formula:


D_{ij}^{n} = \\min(D_{ij}^{n-1}, D_{ik}^{n-1} + D_{kj}^{n-1})

Because this transformation never rewrites elements, which are to be used to calculate the new matrix, we can use the same matrix for both D^{i} and D^{i+1}.

Code

procedure [array] FloydWarshall(D, P)
    for k in 1 to n do
        for i in 1 to n do
            for j in 1 to n do
                if D[i][j] > D[i][k] + D[k][j] then
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = P[k][j]
    return P
    /**
     * Floyd-Warshall algorithm. Finds all shortest paths among all pairs of nodes
     * @param d matrix of distances (Integer.MAX_VALUE represents positive infinity)
     * @return matrix of predecessors
     */
    public static int[][] floydWarshall(int[][] d) {
        int[][] p = constructInitialMatixOfPredecessors(d);
        for (int k = 0; k < d.length; k++) {
            for (int i = 0; i < d.length; i++) {
                for (int j = 0; j < d.length; j++) {
                    if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {
                        continue;                  
                    }
                    
                    if (d[i][j] > d[i][k] + d[k][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                        p[i][j] = p[k][j];
                    }

                }
            }
        }
        return p;
    }

    /**
     * Constructs matrix P0
     * @param d matrix of lengths
     * @return P0
     */
    private static int[][] constructInitialMatixOfPredecessors(int[][] d) {
        int[][] p = new int[d.length][d.length];
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {
                    p[i][j] = i;
                } else {
                    p[i][j] = -1;
                }
            }
        }
        return p;
    }

Asymptotic complexity

The algorithm consists of three loops over all nodes, and the most inner loop contains only operations of a constant complexity. Hence the asymptotic complexity of the whole Floyd-Warshall algorithm is O(\\vert N \\vert ^3), where \\vert N \\vert is number of nodes of the graph.


Example


    \\begin{matrix}
  
      D_{0} = 
      \\begin{pmatrix}
        0 & 5 & \\infty & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & \\infty & 0 & \\infty & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & \\infty & \\infty & 0 \\\\
      \\end{pmatrix}
    
      &
      
      D_{1} =
      
      \\begin{pmatrix}
        0 & 5 & \\infty & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & \\infty & 3 & 0 \\\\
      \\end{pmatrix}    
      
      &
      
      D_{2} =
      
      \\begin{pmatrix}
        0 & 5 & 7 & 2 & \\infty \\\\
        \\infty & 0 & 2 & \\infty & \\infty \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        \\infty & \\infty & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix}       
      \\\\ 
      
      \\\\
      
      D_{3} =
      
      \\begin{pmatrix}
        0 & 5 & 7 & 2 & 14 \\\\
        5 & 0 & 2 & 7 & 9 \\\\
        3 & 8 & 0 & 5 & 7 \\\\
        7 & 12 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      D_{4} =
      
      \\begin{pmatrix}
        0 & 5 & 6 & 2 & 3 \\\\
        5 & 0 & 2 & 7 & 8 \\\\
        3 & 8 & 0 & 5 & 6 \\\\
        7 & 12 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      D_{5} =
      
      \\begin{pmatrix}
        0 & 5 & 6 & 2 & 3 \\\\
        5 & 0 & 2 & 7 & 8 \\\\
        3 & 8 & 0 & 5 & 6 \\\\
        2 & 4 & 4 & 0 & 1 \\\\
        1 & 3 & 5 & 3 & 0 \\\\
      \\end{pmatrix}       
      
      
    \\end{matrix}

Matrix of predecessors

In order to return shortest (longest) paths among all pairs of nodes, we construct during transformations of matrix D_{k} also output matrix P (matrix of predecessors). The matrix can be read as follows: if we want to reconstruct the (shortest) path between nodes i and j, than we look at the element at corresponding coordinates. If its value is 0, than there is no path between these nodes, otherwise the value of the element denotes predecessor of j on the path from i to j. So we repeat this procedure, while the preceding node is not equal to i.


  \\begin{matrix}
  P_{ij}^{(0)} =   \\begin{cases}
   0       & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; i = j\\;\\; or \\;\\; D_{ij} = \\infty \\\\
   i       & \\;\\;\\;\\;\\; \\text{in all other cases}
  \\end{cases}
  
  \\\\\\\\
  
  P_{ij}^{(n)} =   \\begin{cases}
   P_{ij}^{(n-1)}      & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; D_{ij}^{(n-1)} \\leq  D_{ik}^{(n-1)} + D_{kj}^{(n-1)}\\\\
   P_{kj}^{(n-1)}      & \\;\\;\\;\\;\\; \\text{if}\\;\\;\\; D_{ij}^{(n-1)} \\gt  D_{ik}^{(n-1)} + D_{kj}^{(n-1)}
  \\end{cases}  
  
  \\end{matrix}

Code

function getPath(P, i, j)
    if i == j then
        write(i)
    else if P[i][j] = 0 then
        write("Path does not exist")
    else
        getPath(P, i, P[i][j])
        write(j)

Example


    \\begin{matrix}
  
      P_{0} = 
      \\begin{pmatrix}
        0 & 1 & 0 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 0 & 0 & 0 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 0 & 0 & 0 \\\\
      \\end{pmatrix}
    
      &
      
      P_{1} =
      
      \\begin{pmatrix}
        0 & 1 & 0 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 0 & 1 & 0 \\\\
      \\end{pmatrix}    
      
      &
      
      P_{2} =
      
      \\begin{pmatrix}
        0 & 1 & 2 & 1 & 0 \\\\
        0 & 0 & 2 & 0 & 0 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        0 & 0 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix}       
      \\\\ 
      
      \\\\
      
      P_{3} =
      
      \\begin{pmatrix}
        0 & 1 & 2 & 1 & 3 \\\\
        3 & 0 & 2 & 1 & 3 \\\\
        3 & 1 & 0 & 1 & 3 \\\\
        3 & 1 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      P_{4} =
      
      \\begin{pmatrix}
        0 & 1 & 4 & 1 & 4 \\\\
        3 & 0 & 2 & 1 & 4 \\\\
        3 & 1 & 0 & 1 & 4 \\\\
        3 & 1 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix} 
      
      &
      
      P_{5} =
      
      \\begin{pmatrix}
        0 & 1 & 4 & 1 & 4 \\\\
        3 & 0 & 2 & 1 & 4 \\\\
        3 & 1 & 0 & 1 & 4 \\\\
        5 & 5 & 4 & 0 & 4 \\\\
        5 & 5 & 2 & 1 & 0 \\\\
      \\end{pmatrix}       
      
      
    \\end{matrix}

Detection of cycles of (non)negative length

Floyd-Warshall algorithm can be easily modified to detect cycles. If we fill negative infinity value at the diagonal of the matrix and run the algorithm, than the matrix of predecessors will contain also all cycles in the graph (the diagonal will not contain only zeros, if there is a cycle in the graph).

Sources

  • KOLÁŘ, Josef. Teoretická informatika. 2. ed. Praha : Česká informatická společnost, 2004. 205 p. ISBN 80-900853-8-5.
  • HANZÁLEK, Zdeněk. Kombinatorická optimalice, Nejkratší cesty - slides k přednáškám.







       
 

Place for your banner

Here is the position ready for our customer's banners.