Divide and Conquer

Improving Bellman-Ford algorithm

Now let’s look at how we can make a more significant improvement, 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$ ...