Floyd-Warshall algorithm

For more context see All pairs shortest path problem.

Problem

Input: graph $G=(V,E)$ with weights $w:E\to \mathbb{R}$. Assume there are no negative weight cycles.

Output: a $D(u,v)$ that calculates the length of shortest path $u\to v$ for all $(u,v)\in V\times 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\to v$ such that its internal vertices are only in $\{\mathrm{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 $\infty$. Generalized $G$-function:

$$G(u,v,k+1)=\min \{\begin{array}{ll}G(u,v,k)& \text{if we don’t use vertex }k+1\\ G(u,k+1,k)+G(k+1,v,k)& \text{if we use vertex }k+1\end{array}$$

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:

$$\sum _{k=0}^n\left(\sum _u\sum _{v}1\right)=O(n^3)$$

since we do constant time work in each subproblem.