Divide and Conquer

Get to know divide and conquer techniques used to solve the all-pairs shortest paths problem.

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)dist(u, v, l). Here we need to stop at the base case l=1l = 1 instead of l=0l = 0, because a path with at most one edge has no “middle” vertex. To simplify the recurrence slightly, let’s define w(vv)=0w(v\rightarrow v) = 0 for every vertex vv.

dist(u,v)={w(uv) if i=1minx(dist(u,x,l/2)+dist(x,v,l/2))otherwisedist(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 ll is a power of 22, 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)dist(u, v, l) is the true shortest-path distance from uu to vv for all lV1l ≥ V − 1; in particular, we can use l=2lgV<2Vl = 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(V3logV)O(V^3 log V)—we need to consider VV possible values of uu, vv, and xx, but only lgV⌈lgV⌉ possible values of ll.

Fischer and Meyer’s algorithm

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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy