- All-Pairs Shortest Paths
- Transitive Hull
- Minimax Distance
- Maximin Distance
- Safest Path
- What else can you solve with Floyd-Warshall?
- The Rules of the Game
- Examples

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

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

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; }

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]; } } } }

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

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

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

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; }

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]); } } }

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

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

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; }

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])); } } }

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

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; }

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])); } } }

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

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; }

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]); } } }

There are 5 parameters in the algorithm:

**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

Floyd-Warshall works, if ...

**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).

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

*Last modified 2001-02-15*

mdettinger@arsdigita.com |