For more context see All pairs shortest path problem.

Problem

Input:graph $G=(V,E)$ with weights $w:E→R$. Assume there are no negative weight cycles.

Output:a $D(u,v)$ that calculates the length of shortest path $u→v$ for all $(u,v)∈V×V$.

Suppose we number the vertices from 1 to $n$ (how we actually assign the numbers doesn’t really matter. Important part is we differentiate them).

Consider the following $G$-function. We let $G(u,v,k)$ equal the length of the shortest path $u→v$ such that its internal vertices are *only* in ${1..k}$.

- $u$ and $v$ could both be outside the set. Only internal vertices must be in the set.
- A direct edge from $u$ to $v$ does not use an
*internal vertex*and is also considered in the algorithm. See base case below.

Base case is when $k=0$, that is, the path does not contain any internal vertices. If edge $(u,v)$ exists, then return $w(u,v)$, and otherwise return $∞$. Generalized $G$-function:

$G(u,v,k+1)=min{G(u,v,k)G(u,k+1,k)+G(k+1,v,k) if we don’t use vertexk+1if we use vertexk+1 $While this is a top-down approach, essentially we are increasing the size of $k$ at each iteration by including one additional vertex (in this case, denoted by $k+1$). However, we have to consider both the path that doesn’t use $k+1$, and the one that does, because both could be valid.

We can increment $k$ until we include all $n$ vertices, at which point we will have considered the shortest path using the entire graph.

## Runtime

$n_{3}$ subproblems that each take constant time (assuming we cache previous subproblems), so runtime is given by $O(n_{3})$. This is a factor $n$ smaller than the worst case Bellman-Ford.

In a bottom-up approach, the following summation naturally forms:

$k=0∑n (u∑ v∑ 1)=O(n_{3})$since we do constant time work in each subproblem.