For more context see All pairs shortest path problem.
Problem
Input: graph with weights . Assume there are no negative weight cycles.
Output: a that calculates the length of shortest path for all .
Suppose we number the vertices from 1 to (how we actually assign the numbers doesn’t really matter. Important part is we differentiate them).
Consider the following -function. We let equal the length of the shortest path such that its internal vertices are only in .
- and could both be outside the set. Only internal vertices must be in the set.
- A direct edge from to does not use an internal vertex and is also considered in the algorithm. See base case below.
Base case is when , that is, the path does not contain any internal vertices. If edge exists, then return , and otherwise return . Generalized -function:
While this is a top-down approach, essentially we are increasing the size of at each iteration by including one additional vertex (in this case, denoted by ). However, we have to consider both the path that doesn’t use , and the one that does, because both could be valid.
We can increment until we include all vertices, at which point we will have considered the shortest path using the entire graph.
Runtime
subproblems that each take constant time (assuming we cache previous subproblems), so runtime is given by . This is a factor smaller than the worst case Bellman-Ford.
In a bottom-up approach, the following summation naturally forms:
since we do constant time work in each subproblem.