The motivation

What if we wanted to find all pairwise shortest path? (APSP)?

We can use nn Bellman-Ford steps, which takes n2mn^2m complexity. If there are no negative edges, we can use nn steps of djikstra’s algorithm, which takes n2logn+nmn^2\log n + nm.

If mn2m \propto n^2, then BF takes n4n^4 complexity, and Djikstra takes n2logn+n3n^2\log n + n^3, which is OK but can we just do it in O(n3)O(n^3) steps, regardless of edge weight sign?



Here, we put on our dynamic programming thinking caps. What sort of subproblem can we design? How about an array D(k)[i,j]D^{(k)}[i, j] that is the shortest path between i,ji, j such that all the vertices between i,ji, j are vertices 1,...k1, ... k.

This actually a little bit counterintuitive. The knee-jerk adaptation is to use bellman-ford but pairwise. In that case, DD would be the shortest path such that the number of vertices between i,ji, j are less than kk. However, you can show to yourself that this yields O(n4)O(n^4) complexity and is not good.

What happens at each step

You would initialize D(0)D^{(0)} as the weighted adjacency matrix (and non-edges are infinite). This because direct edges have no vertices between them, which satisfies the definition of DD. Then, you would do the following:

  1. Select a pair of nodes A,CA, C (represented as an element in DD).
  1. Try if AkCA→k→C is of lower weight than ACA→C. If you can find one, update the distance in DD. If not, keep what you have. You can use AkA→k and kCk→C as defined in your DD.

Inductively, it should be easy to show that you keep the inductive definition of DD after doing this step.

Much like Bellman-Ford, you can show that you only need n1n-1 steps to complete. In each step, you iterate through n2n^2 pairs of vertices, yielding a final complexity of O(n3)O(n^3).

Algorithm box

Detecting negative cycles

If there are negative cycles, then D[v,v]<0D[v, v] < 0. Because negative cycles necessairly mean that you can circle back to where you started and be better off.