Divide and Conquer

Improving the Bellman-Ford algorithm

We can make a more significant improvement to the Bellman-Ford algorithm, suggested by Michael Fischer and Albert Meyer in 1971. Bellman’s recurrence breaks the shortest path into a slightly shorter path and a single edge by considering all possible predecessors of the target vertex. Instead, let’s break the shortest paths into two shorter shortest paths at the middle vertex. This idea gives us a different recurrence for the same function $dist(u, v, l)$. Here we need to stop at the base case $l = 1$ instead of $l = 0$, because a path with at most one edge has no “middle” vertex. To simplify the recurrence slightly, let’s define $w(v\rightarrow v) = 0$ for every vertex $v$.

$$dist(u,v) = \begin{cases} & w(u\rightarrow v) \hspace{4.26cm}\text{ if }i=1 \\ & \underset{x}{min} (dist(u,x,l/2) + dist(x,v,l/2)) \hspace{0.4cm} otherwise \end{cases}$$

As stated, this recurrence only works when $l$ is a power of $2$, since otherwise, we might try to find the shortest path with (at most) a fractional number of edges! But that’s not really a problem; $dist(u, v, l)$ is the true shortest-path distance from $u$ to $v$ for all $l ≥ V − 1$; in particular, we can use $l = 2^{⌈lg V ⌉} < 2V$.

Once again, a dynamic programming solution is straightforward. Even before we write down the algorithm, we can tell the running time is $O(V^3 log V)$—we need to consider $V$ possible values of $u$, $v$, and $x$, but only $⌈lgV⌉$ possible values of $l$.

Fischer and Meyer’s algorithm

In the following pseudocode for Fischer and Meyer’s algorithm, the array entry $dist[u, v, i]$ stores the value of $dist(u, v, 2^i )$.