Dijkstra and shortest paths · 3 of 4
Bellman-Ford
Find distances when weights can be negative by relaxing every edge in rounds, detect a negative cycle, and limit the number of edges on a path.
- Algorithms, Chapter 8: Shortest paths Section 8.7 proves that after i rounds every tentative distance is at most the length of the shortest path with at most i edges, and turns that bound into a test for negative cycles. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)
- Bellman-Ford Algorithm A proof of the round bound, early stopping, rebuilding the route and finding a negative cycle with one more round. cp-algorithms.com (opens in a new tab)
- Finding a negative cycle in the graph Prints the cycle itself by walking back through the recorded parents from a vertex the last round lowered, and finds one with Floyd-Warshall as well. cp-algorithms.com (opens in a new tab)