Dynamic programming solution to the Single source shortest path problem that can also detect negative weight cycles, which means it won’t get stuck in an infinite loop like Dijkstra’s algorithm.
Problem
Input: graph with weights with potential negative weight edge cycles, source vertex , target vertex .
Output: shortest path from to , otherwise a negative weight cycle has been detected.
Intuition, top-level question
From Characterizations about optimal shortest paths, we know all subpaths in the shortest path are also shortest paths. This naturally leads to an algorithm where we find a potential shortest subpath and build on top of it to find the shortest path for .
The shortest path for uses at most vertices, and is therefore at most of length (this can happen if, for example, our graph was simply a line). So we need to cover every case less than or equal to that.
- To enable DP, generalize this for a path of any length . This way we can slowly build up to (if we’re doing bottom-up).
- Then, the shortest path from to using at most hops is the shortest path of using hops, plus the weight of , where , the neighbors of .
- It could be the case that with hops is shorter. So the final answer takes the minimum of the two.
-function
The -function is as follows:
Base case occurs when , in which we case we check if . If yes, then return 0 (distance to itself is zero). Otherwise, return infinity.
Algorithm
The -function describes the algorithm in a top-down manner. In practice, Bellman-Ford is usually implemented bottom-up.
- Maintain the shortest path from to all other vertices in a function which records the length of the shortest path .
- Initialize and for all other .
- We repeat for rounds. In each round, iterate through every edge and update .