Indian Computing Olympiad

Shortest paths

All pairs shortest paths: the Floyd-Warshall algorithm

Here is another way to compute shortest paths. We compute

• shortestpath(s,t,i) : shortest path from s to t that uses at most i edges

Initially

• shortestpath(s,t,0) = 0, if s = t
                                 infinity, otherwise
• shortestpath(s,t,i+1) =
            min (
                shortestpath (s,t,i),
                min_{k} shortestpath(s,k,i) + W[k,t]
            )

Note that the shortest path from s to t will never go through a loop, because we can remove the loop and get a shorter path. Thus, we only need to find paths of length at most N-1.

This is called the Floyd-Warshall algorithm.

We can compute this by storing the values in a 3 dimensional array SP. Assume the vertices are numbered [1,2,...,n]

We maintain the value shortestpath(s,t,i) as SP[s,t,i].

      SP[s,t,0] = 0 if s = t, infinity otherwise

      for (i = 1; i < n; i++){
          for (t = 1; t <= n; t++){
              /*
                 SP[s,t,i] = min (SP[s,t,i-1],
                                  min SP[s,u,i]+W[u,t])
                                   u
              */
              SP[s,t,i] = SP[s,t,i-1];
              for (u = 1; u <= n; u++){
                  SP[s,t,i] = min(SP[s,t,i],SP[s,u,i-i]+W[u,t]);
              }
          }
      }
      

This algorithm takes time n³ to compute SP[s,t,n-1]. Note that to compute SP[s,t,i], we only need
SP[s,t,i-1], so we can make do with just two 2-dimensional arrays of size n×n that we use alternately, rather than a 3-dimensional array of size n×n×n.

Claim: Floyd-Warshall can compute shortest paths in situations that Dijkstra does not.

Suppose we can have negative edge weights. If we have cycles with a total negative weight, the notion of shortest path does not make sense because we can go around the negative cycle as many times as we want and reduce the overall weight. So, let us permit negative edge weights, provided they do not induce negative cycles.

• Will Dijkstra's algorithm work in graphs with negative edges?
• How will Floyd-Warshall work if there are negative edges? How many iterations will it take? (Note that since there are no negative weight cycles, any cycle we visit will have a positive weight and can hence be eliminated from any shortest path.)

Video lectures on shortest paths, NPTEL online course on Design and Analysis of Algorithms

• All pairs shortest paths: Floyd-Warshall algorithm (Lecture slides)

• Single source shortest paths with negative edge weights, Bellman-Ford algorithm (Lecture slides)