Last updated on: 10 November 2008 06:01:19 PM

This page will be updated with the following items:
-. Too brief for a topic as "difficult" as this... I'll add more information later...

Go to Programming Section

Contents:

1. Introduction to Graph
2. Searching a Graph
3. Finding Connected Components (Flood Fill)
4. Minimum Spanning Trees (MST)
5. Single-Source Shortest Paths
6. All-Pairs Shortest Paths
 - Floyd Warshall
 - Johnson (later)
7. Advanced Algorithms

Reference:

1. Introduction to Algorithms [CLR], Chapter 26
2. http://www.aduni.org/courses/algorithms/handouts/Reciation_07.html

Floyd Warshall

Given a directed graph, the Floyd-Warshall All Pairs Shortest Paths algorithm computes the shortest paths between each pair of nodes in O(n^3). A complete detail can be found in CLR chapter 26. In this page, I list down the Floyd Warshall and its variant plus the source codes.

Given:
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++) /* k -> is the intermediate point */
  for (i=0;i<n;i++) /* start from i */
    for (j=0;j<n;j++) /* reaching j */
      /* if i-->k + k-->j is smaller than the original i-->j */
      if (d[i][k] + d[k][j] < d[i][j]) {
        /* then reduce i-->j distance to the smaller one i->k->j */
        d[i][j] = d[i][k]+d[k][j];
        /* and update the predecessor matrix */
        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,p[i][j]);
  print(j);
}

Variant of Floyd Warshall

1. Transitive Hull

Given a directed graph, the Floyd-Warshall algorithm can compute the Transitive Hull in O(n^3). Transitive means, if i can reach k and k can reach j then i can reach j. Transitive Hull means, for all vertices, compute its reachability.

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] is true if d[i][j] already true
         or if we can use k as intermediate vertex to reach j from i,
         otherwise, d[i][j] is false */
      d[i][j] = d[i][j] || (d[i][k] && d[k][j]);

2. 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(n^3). For example of a minimax problem, refer to the Valladolid OJ problem below.

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

3. MaxiMin Distance

You can also compute the maximin distance with the Floyd-Warshall algorithm. Maximin is the reverse of minimax. Again, look at Valladolid OJ problem given below to understand maximin.

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

4. 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 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]);

PREVIOUS - NEXT