Floyd-Warshall (ADU Feb 15)

Floyd-Warshall (ADU Feb 15)

a WimpyPoint presentation owned by Mark Dettinger

All-Pairs Shortest Paths


Given a directed graph, the Floyd-Warshall algorithm computes the shortest paths between each pair of nodes in O(n3).

w : edge weights
d : distance matrix
p : predecessor matrix

w[i][j] = length of direct edge between i and j
d[i][j] = length of shortest path between i and j
p[i][j] = on a shortest path from i to j, p[i][j] is the last node before j, i.e. i -> ... -> p[i][j] -> j

Initialization

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
    d[i][j] = w[i][j];
    p[i][j] = i;
  }
}
for (i=0; i<n; i++) {
  d[i][i] = 0; 
}

The Algorithm

for (k=0; k<n; k++)
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      if (d[i][k] + d[k][j] < d[i][j]) {
        d[i][j] = d[i][k] + d[k][j];
        p[i][j] = p[k][j];
      }
    }
  }
}

Note

In the k-th iteration of the outer loop, we try to improve the currently known shortest paths by considering k as an intermediate node. Therefore, after the k-th iteration we know those shortest paths that only contain intermediate nodes from the set {0, 1, 2,...,k}. After all n iterations we know the real shortest paths.

Constructing a Shortest Path

print_path (int i, int j) {
  if (i!=j) {
    print_path(i,pred[i][j]);
  }
  print(j);
}

    
    
    
    

Transitive Hull


Given a directed graph, the Floyd-Warshall algorithm can compute the transitive hull in O(n3).

w : adjacency matrix
d : transitive hull

w[i][j] = edge between i and j (0=no edge, 1=edge)
d[i][j] = 1 if and only if j is reachable from i

Initialization

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
    d[i][j] = w[i][j];
  }
}
for (i=0; i<n; i++) {
  d[i][i] = 1; 
}

The Algorithm

for (k=0; k<n; k++)
  for (i=0; i<n; i++)
    for (j=0; j<n; j++)
      d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
    }
  }
}

    
    
    
    

Minimax Distance


Given a directed graph with edge lengths, the Floyd-Warshall algorithm can compute the minimax distance between each pair of nodes in O(n3).

w : edge weights
d : minimax distance matrix
p : predecessor matrix

w[i][j] = length of direct edge between i and j
d[i][j] = length of minimax path between i and j

Initialization

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
    d[i][j] = w[i][j];
  }
}
for (i=0; i<n; i++) {
  d[i][i] = 0; 
}

The Algorithm

for (k=0; k<n; k++) {
  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
    }
  }
}

    
    
    
    

Maximin Distance


You can also compute the maximin distance with the Floyd-Warshall algorithm.

w : edge weights
d : maximin distance matrix
p : predecessor matrix

w[i][j] = length of direct edge between i and j
d[i][j] = length of maximin path between i and j

Initialization

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
    d[i][j] = w[i][j];
  }
}
for (i=0; i<n; i++) {
  d[i][i] = 0; 
}

The Algorithm

for (k=0; k<n; k++) {
  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
    }
  }
}

    
    
    
    

Safest Path


Given a directed graph where the edges are labeled with survival probabilities, you can compute the safest path between two nodes (i.e. the path that maximizes the product of probabilities along the path) with --- try to guess --- Floyd-Warshall!

w : edge weights
p : probability matrix

w[i][j] = survival probability of edge between i and j
p[i][j] = survival probability of safest path between i and j

Initialization

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
    p[i][j] = w[i][j];
  }
}
for (i=0; i<n; i++) {
  p[i][i] = 1; 
}

The Algorithm

for (k=0; k<n; k++) {
  for (i=0; i<n; i++) {
    for (j=0; j<n; j++) {
      p[i][j] = max(p[i][j], p[i][k] * p[k][j]);
    }
  }
}

    
    
    
    

What else can you solve with Floyd-Warshall?


There are 5 parameters in the algorithm:
    
    
    
    

The Rules of the Game


Floyd-Warshall works, if ... A proof is given in CLR, page 570.
    
    
    
    

Examples


    
    
    
    

Last modified 2001-02-15


mdettinger@arsdigita.com