All-Pairs Shortest Paths

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

Constructing a Shortest Path

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

Transitive Hull

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

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

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

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?

• S = the set of values that edges can have
• seq = the sequential operator for combining two paths
• par = the parallel operator for combining two paths
• 0 = the value that represents a missing edge
• 1 = the value that represents an empty path

The Rules of the Game

• S is closed under par and seq.
• par is associative, commutative and idempotent (a par a = a).
• seq is associative.
• seq distributes over par (a seq (b par c) = (a seq b) par (a seq c).
• 0 is an annihilator for seq (a seq 0 = 0 seq a = 0).
• 0 is an identity for par (a par 0 = 0 par a = a).
• 1 is an identity for seq (a seq 1 = 1 seq a = a).

Examples

• Guaranteed Intermediate Stops (Floyd-Warshall works)
• Resistor Networks (Floyd-Warshall fails)

Last modified 2001-02-15