Shortest Paths Via Dynamic Programming

Bellman-Ford but really this time

Let G = (V, E) be a directed graph with possibly negative edge weights w: E \to \mathbb{R} and a source vertex s. We previously saw an O(|E||V|) time algorithm for single source shortest paths from s that could also be used to detect negative weight cycles. The main idea behind that algorithm was to build a directed acyclic graph via layering that let us find the minimum length of paths with a prescribed number of edges. This algorithm has a few downsides, however including the need to use O(|E||V|) space (not that we typically worry about space usage in this class) and not quite matching Ford’s slick SSSP framework. Today, we’ll begin by rediscovering essentially the same algorithm using a different viewpoint and see how that leads to some improvements that make the whole thing incredibly clean at the end. We’ll attack the problem using a more direct application of dynamic programming.

Let \mathit{distance}(v) denote the distance from s to v. For the case of G being a dag, we had the following recurrence: \mathit{distance}(v) = \begin{cases} 0 & \text{if \(v = s\)} \\ \min\limits_{u \to v} (\mathit{distance}(u) + w(u \to v)) & \text{otherwise.} \end{cases}

However, for a general directed graphs G, this recurrence has a serious flaw. If there are any cycles, then the recurrence is not well-defined. In particular, the naïve recursive algorithm would get stuck in a infinite loop!

So let’s add an additional parameter to our recurrence that will get smaller. Recalling what we did last time using layering, let’s parameterize by the number of edges in a walk to v. Let \mathit{distance}_{\leq i}(v) denote the length of the shortest walk from s to v consisting of at most i edges. Assuming there are no negative weight cycles, \mathit{dist}(v) = \mathit{dist}_{\leq |V| - 1}(v), because any simple path has at most |V| - 1 edges. We’re using “at most” here instead of “exactly” to allow for some practical optimizations later.

Now we need to find a recurrence for this function. Outside of the easy base cases, there are two possibilities. Either the shortest such walk to v with at most i edges has at most i - 1 edges or it has exactly i \leq (i - 1) + 1 edges, the last edge being some u \to v. Whether or not G has a negative weight cycle, we get the following recurrence. \mathit{distance}_{\leq i}(v) = \begin{cases} 0 & \text{if \(i = 0\) and \(v = s\)} \\ \infty & \text{if \(i = 0\) and \(v \neq s\)} \\ \min \left\{\begin{gathered} \mathit{distance}_{\leq i - 1}(v) \\ \min\limits_{u \to v} (\mathit{distance}_{\leq i - 1}(u) + w(u \to v)) \end{gathered}\right\} & \text{otherwise.} \end{cases}

Now it’s time to memoize. Assuming there are no negative weight cycles, it suffices to consider 0 \leq i \leq |V| - 1, and we also need to consider each vertex (v \in V). For consistency with what’s coming later, we’ll store the results in an array \mathit{distance}[0~..~|V| - 1, V] (where the second parameter is indexed by the vertices themselves). Recursive calls always use a smaller values of i and perhaps any vertex, so we should make i our outer loop variable going in increasing order. The resulting algorithm was discovered by Bellman. Note that the base cases are handled outside the main loops, again for consistency with what’s coming later.

Variable i takes on O(V) values and we look at every vertex and edge at most once per choice of i. Assuming the graph is connected, the running time is O(VE), just like in the previous lecture.

However, this algorithm still isn’t the one most people familiar with shortest paths will think of, and it still has the issue of using O(|E||V|) space. Let’s see if we can simplify things somewhat.

First, we’re going through every edge exactly once in the innermost for loop, but it’s not actually important to consider them in any particular order. Let’s move the edges for loop one level out.

Second, we’re going to change the indices in the last two lines to use i instead of i - 1.

The result of the previous change is that we might find slightly shorter distances a bit faster than what we’re supposed, to meaning \mathit{distance}[i, v] \leq \mathit{distance}_{\leq i}(v) instead of them being equal. However, the value being stored is still based on summing edges weights along a real walk.

Finally, we may now observe how in each iteration of the outer loop, we’re just copying a row from the DP array to modify and then ignoring the original copy forever. Let’s skip the copying and work directly on the first array we make.

Great! This is more-or-less exactly how the well-known Bellman-Ford algorithm computes distances. All that remains is to add the FordSSSP language and stop early if the loops no longer do any work. Finally, we can put our negative weight cycle check from last time back in.

So to summarize our work on SSSP:

• dag with arbitrary edge weights: Use DagSSSP in O(V + E) time.
• Any unweighted graph: Use BFS in O(V + E) time.
• Any non-dag with no (or very few) negative weight edges: Use Dijkstra in O(E \log V) (or close to it) time.
• Any non-dag with many negative edge weights but no negative weight cycles: Use BellmanFord in O(VE) time.

All-pairs shortest paths

So now we have exhaustively covered the problem of finding shortest paths from a single vertex s to all other vertices. But what if we want to know more than just those shortest paths? For example, maybe we want to pre-compute travel time between several pairs of cities. In the all pairs shortest paths (APSP) problem, we’re given a directed graph G = (V, E) with edge weights w : E \to \mathbb{R}, and want to compute \mathit{dist}(u, v), the distance from u to v for every ordered pair of vertices (u, v). We’ll also want to have \mathit{dist}(u, v) = \infty if there is no path from u to v. (We might also want to know \mathit{pred}(u, v), the second-to-last vertex on the shortest path from u to v, but we’re not going to worry about the trivial extra details to compute that in this lecture.) We’ll assume there are no negative weight cycles for the rest of this lecture. We don’t know how to efficiently deal with them even working with single sources, and APSP is strictly more general.

The most obvious algorithm for APSP is to run an SSSP algorithm once per source u. If edge weights positive, we could use Dijkstra’s algorithm for this purpose. We’d be running if |V| times, so the total running time would be O(|V||E| \log |V|) = O(|V|^3 \log |V|) if the graph is dense (has almost all possible edges). Things get worse if there are lots of negative weight edges. We’d have to run Bellman-Ford |V| times, and that would lead to a total running time of O(|V||E||V|) = O(|V|^4) if the graph is dense! That final running time is pretty bad! Can we do better?

There’s a method in the textbook called Johnson’s algorithm. It’s really interesting, in my opinion, and I highly recommend you give it a look, but you can’t really do anything with the theory it’s based on unless you unless you take 473 or do certain types of optimization. So instead of spending time on Johnson’s algorithm, we’re going to use APSP as an excuse to practice more dynamic programming. (Our last opportunity to do so together 😢).

Dynamic programming by number of edges

Like we saw earlier, there’s an “obvious” recursive definition for \mathit{dist}(u, v) that completely fails if the graph contains cycles. \mathit{dist}(u, v) = \begin{cases} 0 & \text{if \(u = v\)} \\ \min\limits_{x \to v} (\mathit{dist}(u, x) + w(x \to v)) & \text{otherwise.} \end{cases}

It’s easily fixed if we add another parameter tracking the length of the path. Let \mathit{dist}(u, v, \ell) denote the length of the shortest path from u to v that uses at most \ell edges (we’ll use i for something else later). As before \mathit{dist}(u, v) = \mathit{dist}(u, v, \ell). \mathit{dist}(u, v, \ell) = \begin{cases} 0 & \text{if \(\ell = 0\) and \(v = s\)} \\ \infty & \text{if \(\ell = 0\) and \(u \neq v\)} \\ \min \left\{\begin{gathered} \mathit{dist}(u, v, \ell - 1) \\ \min\limits_{x \to v} (\mathit{dist}(u, x, \ell - 1) + w(x \to v)) \end{gathered}\right\} & \text{otherwise.} \end{cases}

And again as before, each recursive call reduces the final parameter, meaning we should iterate over its values in ascending order of \ell and then the others in whatever order The resulting algorithm was discovered by Shimbel in 1954.

And again again, we can simplify things by simply iterating over all edges instead of doing so tail-by-tail, and by dropping the third parameter from the memoization table. The final result looks a lot like Bellman-Ford.

In this form, it’s relatively clear that the running time is O(V^2 E) = O(V^4). Oh no, we didn’t improve anything. Maybe that shouldn’t be a surprise, though. We never change the first parameter when working with the \mathit{dist} array, so we’re really just interleaving V independent instances of Bellman-Ford. But we’re computing so many (partial) distances. Surely, there’s some way to have the problems rely on one-another so we can get a speedup.

Divide-and-conquer

TODO: Clean up this section.

• One way to think of the previous recurrence is that we’re breaking a path of length at most \ell into a path of length at most \ell - 1 plus a single edge, and therefore, the dependency graph itself is going to have paths of length \ell.
• But what if we recurse in a way that bottoms out more quickly?
• In particular, let’s try splitting the path at the middle vertex.
• For simplicity, let w(v \to v) = 0 and w(u \to v) = \infty whenever u \to v \notin E. We have the following recurrence. [That i in the base case should be an \ell.]
• This recurrence gets a bit wonky if \ell isn’t a power of two, but we can deal with that issue by setting \ell = 2^{\lceil \lg V \rceil} < 2V in the top level calls.
• We still need to consider different \ell from low to high and then the vertices in arbitrary order, but now each \ell we consider is each of \lceil \lg V \rceil powers of 2. We’ll use i as the actual parameter in our outer loop/index in our data structure, having each \mathit{dist}[u, v, i] store \mathit{dist}(u, v, 2^i).
• The resulting algorithm was suggested by Fischer and Meyer in 1971.
• This one runs in O(V^3 \log V) time!
• We can even clean it up similar to before without sacrificing the running time. This variant was described by Layzorek et al. in 1957. (Weird how people keep rediscovering the same algorithm but with more complicated code.)

Dynamic programming by restricting vertices

We’re now matching the time it takes to run Dijkstra V times. But can we do better? Yes! And the trick is to use a different third parameter for the recurrence: which vertices can a path pass through.

We say a path passes through a vertex x if it both enters and leaves x. For example, w \to x \to y \to z passes through both x and y but not w and z. Number the vertices arbitrarily from 1 to V. We define a path \pi(u, v, r) as the shortest path from u to v that passes through only vertices numbered at most r. The true shortest path from u to v is \pi(u, v, V).

Similar to how a path with at most \ell edges may or may not need all \ell edges, \pi(u, v, r) may or may not pass through r. And the only option for \pi(u, v, 0) is the edge u \to v (we’ll always assume it exists and give it a weight of \infty otherwise). Now, let’s redefine \mathit{dist}(u, v, r) to be the length of \pi(u, v, r) (implying \mathit{dist}(u, v) = \mathit{dist}(u, v, V)). We see \mathit{dist}(u, v, r) = \begin{cases} w(u \to v) & \text{if \(r = 0\)} \\ \min \left\{\begin{gathered} \mathit{dist}(u, v, r - 1) \\ \mathit{dist}(u, r, r - 1) + \mathit{dist}(r, v, r - 1) \end{gathered}\right\} & \text{otherwise.} \end{cases}

Similar to before, we can do dynamic programming by evaluating subproblems by increasing value of r and arbitrary order for u and v. This recursive structure was first proposed by Kleene (surprise!) in 1951 while showing that every DFA has an equivalent regular expression.

This one runs in O(V^3) time! Like with the “at most \ell edges” based algorithms, we can ignore final dimension of the DP table. The resulting algorithm is usually attributed to Floyd and Warshall.

Updates!

• Peer-reviewed faster SSSP with or without negative edges
• Claimed faster APSP by Alman and Williams (found by Anthropic)
• Mixed up APSP still works if you repeat the whole thing three times