21  All-pairs shortest paths

This section uses dynamic programming to solve all-pairs shortest paths.

Objectives. After learning this material, you should be able to:

• Execute the Floyd-Warshall algorithm on example inputs.
• Identify the DP components of the Floyd-Warshall algorithm.
• Solve new DP problems involving adding an extra dimension.

21.1 The problem and algorithm

In the all-pairs shortest paths problem, our goal is to output a data structure giving the shortest path from any starting point to any end point.

• Input: Graph \(G = (V,E)\) with \(n\) vertices, weighted, directed, with no negative cycles.
• Output: two-dimensional array $D[u,v] = $ length of shortest path from \(u\) to \(v\).

The challenge here is that \(D[u,v]\) does not give us any useful subproblem to work with. We need a new clever idea to introduce simpler subproblems that enable us to build up a solution. As with knapsack, we’ll introduce an extra variable. The key idea is to consider paths that only use a subset of the vertices. We can grow the subset to build up more complex solutions.

Subproblem definition. Let $d[u,v,k] = $ length of the shortest path from \(u\) to \(v\) using as intermediate nodes only vertices \(1,\dots,k\).

Final solution. In particular, with \(n\) vertices, $d[u,v,n] = $ the length of the shortest path from \(u\) to \(v\) using all vertices. So if we set \(D[u,v] = d[u,v,n]\) for all \(u,v\), this will be correct.

Recurrence. For the base cases, we set \(d[u,u,0] = 0\) for all \(u\). Then, for all edges \((u,v)\) with length \(w[u,v]\), we set \(d[u,v,0] = w[u,v]\). For all other pairs, we set \(d[u,v,0] = \infty\).

For the inductive case with \(k \geq 1\), imagine we’ve solved \(d[u,v,k-1]\) for all \(u,v\) and now we want to compute \(d[u,v,k]\). We set: \[\begin{equation} d[u,v,k] = \min\begin{cases} d[u,v,k-1] \\ d[u,k,k-1] + d[k,v,k-1] \end{cases} . \end{equation}\] Informally, this says we can either use the old route that didn’t include \(k\) at all, or we can include \(k\). If we do, then we must route from \(u\) to \(k\) somehow, using distance \(d[u,k,k-1]\), and then route to \(v\) somehow, using distance \(d[k,v,k-1]\).

Claim 1 The recurrence is correct, i.e. $d[u,v,k] = $ the length of the shortest path from \(u\) to \(v\) that goes through only vertices \(1,\dots,k\).

Proof. The shortest path from \(u\) to \(v\), using only intermediate vertices \(1,\dots,k\), either uses vertex \(k\) or it doesn’t. Suppose it doesn’t. Then \(d[u,v,k] = d[u,v,k-1]\), by definition.

Suppose it does. Then the shortest path using \(1,\dots,k\) has the form \(u, \dots, k, \dots, v\). Then the portion \(u,\dots,k\) must be a shortest path from \(u\) to \(k\) using intermediate vertices \(1,\dots,k-1\). (Otherwise, we could take the shortest path and shorten the distance from \(u\) to \(v\), a contradiction.) Similarly, the portion \(k,\dots,v\) must be a shortest path from \(k\) to \(v\). So in this case, \(d[u,v,k] = d[u,k,k-1] + d[k,v,k-1]\).

Since the shortest path must be one of these two cases, it is the smaller of the two.

Putting the pieces together, we get this algorithm:

Algorithm 21.1  

floyd_warshall(G, w):
   let d[u,v,0] = 0        if u==v,
                = w[u,v]   if (u,v) is an edge,
                = infinity otherwise
   for k = 1 to n:
      for u = 1 to n:
         for v = 1 to n:
            set d[u,v,k] = min(d[u,v,k-1], d[u,k,k-1] + d[k,v,k-1])
   let D[u,v] = d[u,v,n] for all u,v
   return D

Correctness. As usual with dynamic programming, correctness follows from above arguments that the subproblem, final solution, and recurrence are correct.

Efficiency. Initialization requires up to \(O(n^2)\) time, since we set \(d[u,v,0]\) for all pairs of nodes. Similarly, returning the solution requires constructing an \(O(n^2)\) array, which has the same running time. There are three nested loops, each with \(n\) iterations, and constant-time operations within each. So the running time is dominated by \(O(n^3)\).

The space includes \(D\) and local variables, but is dominated by \(d\) which uses \(O(n^3)\) space.

21.1.1 Reconstructing the solution

In this case, we obtained the lengths of the shortest paths, but not the actual paths themselves. As usual, reconstructing the solution will involve remembering the choices made when solving the subproblems, but here the full procedure is a bit unusual.

A merge approach. The most direct approach, applying our usual DP approach, is as follows. Let us create a variable inter[u,v] standing for “intermediate” vertices between \(u\) and \(v\). Initially, we set inter[u,v] = none for all u,v. Whenever we make a modification d[u,v,k] = d[u,k,k-1] + d[k,v,k-1], we set inter[u,v] = k.

Now, we can reconstruct the path as follows:

• If inter[u,v] == none, then we must have followed an edge directly from \(u\) to \(v\), so the path is just \(u,v\).
• Otherwise, if inter[u,v] == k, then we make a recursive call to reconstruct the path from \(u\) to \(k\), another to get the path from \(k\) to \(v\), and we concatenate these.

A “next” approach. Notice that if a shortest path is of the form \(u,x,\dots,v\), then it is also true that \(x,\dots,v\) is a shortest path from \(x\) to \(v\). This implies that we only need to know, for each pair \(u,v\), what the “next” vertex is on a shortest path. If we find that it is \(x\), then we continue by finding the next vertex on the path from \(x\) to \(v\), etc.

So initialize next[u,v] = v if there is an edge \((u,v)\) and otherwise next[u,v] = none. Whenever we make a modification d[u,v,k] = d[u,k,k-1] + d[k,v,k-1], we can set next[u,v] = next[u,k], since the shortest path to \(v\) proceeds by first taking the shortest path to \(k\).

In this case, reconstruction is even easier:

• Begin the path with u.
• Let x = next[u,v].
• Add x to the path.
• If x == v, stop.
• Otherwise, let x = next[x,v], go to step 3, and continue.