Floyd-Warshall Algorithm


The Floyd-Warshall algorithm is an efficient DynamicProgramming algorithm that computes the shortest path between all pairs of vertices in a directed (or undirected) graph. This is arguably the easiest-to-implement algorithm around for computing shortest paths on programming contests.

// Basic Floyd Warshall Implementation
// input:
//     d is a distance matrix for n nodes.
//         e.g. d[i][j] is the distance to move directly from i to j.
//         if no direct link from i to j then initialize d[i][j] = Infinity.
//         the distance from a node to itself is 0. Initialize d[i][i] = 0 for all i.
//     p is a predecessor matrix. it enables you to reconstruct the shortest paths.
//         p[i][j] should be initialized to i.
// output:
//     d[i][j] contains the total cost along the shortest path from i to j.
//     p[i][j] contains the predecessor of j on the shortest path from i to j.
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];
      }

// Recursive function to reconstruct the shortest path from i to j
// using the predecessor matrix computed above
print_path (int i, int j) {
  if (i!=j)
    print_path(i,p[i][j]);
  print(j);
}

Applications


// Transitive closure variant of Floyd-Warshall
// input: d is an adjacency matrix for n nodes.
//     reachability of a node to itself e.g. d[i][i] should be initialized to 1.
// output: d[i][j]=1 will mean j can be reached from i.
for(k=0;k<n;k++)
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      if(d[i][k]=='1' && d[k][j]=='1') d[i][j]='1';


// Minimax variant of Floyd-Warshall example
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
//     the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the minimax path from i to j.
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 variant of Floyd-Warshall example
// input: d is an distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
//     the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the maximin path from i to j.
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 variant of Floyd-Warshall example
// input: p is an probability matrix (probability of survival) for n nodes
//     e.g. p[i][j] is the probability of survival moving directly from i to j.
//     the probability from a node to itself e.g. p[i][i] should be initialized to 1
// output: p[i][j] will contain the probability of survival using the safest path from i to j.
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]);
Computer Science @ George Mason University