| Bellman–Ford algorithm | |
|---|---|
 | |
| Class | Single-source shortest path problem (for weighted directed graphs) |
| Data structure | Graph |
| Worst-case performance | Θ(|V|) |
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs with negative edge weights. The algorithm was first proposed by 1956, respectively. Edward F. Moore also published a variation of the algorithm in CITEREFMoore1959</span>"}]]}'>1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.
Negative edge weights are found in various applications of graphs. This is why this algorithm is useful. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report the negative cycle.
|V| is the number of vertices in the graph.In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra's algorithm. The intermediate answers and the choices among equally short paths depend on the order of edges relaxed, but the final distances remain the same.
Bellman–Ford runs in |E| are the number of vertices and edges respectively.
function BellmanFord(list vertices, list edges, vertex source) is // This implementation takes in a graph, represented as // lists of vertices (represented as integers [0..n-1]) and // edges, and fills two arrays (distance and predecessor) // holding the shortest path from the source to each vertex distance := list of size n predecessor := list of size n // Step 1: initialize graph for each vertex v in vertices do // Initialize the distance to all vertices to infinity distance[v] := inf // And having a null predecessor predecessor[v] := null // The distance from the source to itself is zero distance[source] := 0 // Step 2: relax edges repeatedly repeat |V|−1 times: for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then distance[v] := distance[u] + w predecessor[v] := u // Step 3: check for negative-weight cycles for each edge (u, v) with weight w in edges do if distance[u] + w < distance[v] then predecessor[v] := u // A negative cycle exists; // find a vertex on the cycle visited := list of size n initialized with false visited[v] := true while not visited[u] do visited[u] := true u := predecessor[u] // u is a vertex in a negative cycle, // find the cycle itself ncycle := [u] v := predecessor[u] while v != u do ncycle := concatenate([v], ncycle) v := predecessor[v] error "Graph contains a negative-weight cycle", ncycle return distance, predecessorSimply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value.
The core of the algorithm is a loop that scans across all edges at every loop. For every v, following the predecessor trail recorded in distance[v] is a lower bound to the length of any path from source to |V|−1 edges, the edges must be scanned O(|V|⋅|E|) to v1, v2, ..., v|V|, relaxing each outgoing edge from that vertex in Ef. Each vertex is then visited in the order {{!}}''V''{{!}}</sub>, ''v''<sub>{{!}}''V''{{!}}−1</sub>, ..., ''v''<sub>1</sub>"}},"i":0}}]}'/>v|V|, v|V|−1, ..., v1, relaxing each outgoing edge from that vertex in Eb. Each iteration of the main loop of the algorithm, after the first one, adds at least two edges to the set of edges whose relaxed distances match the correct shortest path distances: one from Ef and one from Eb. This modification reduces the worst-case number of iterations of the main loop of the algorithm from |V|/3.
Fineman (2024), at Georgetown University, created an improved algorithm that with high probability runs in
- 1 2 3 4 Bang-Jensen & Gutin (2000)
- 1 2 Lecture 14 stanford.edu
- ↑ Schrijver (2005)
- ↑ Sedgewick (2002).
- ↑ Kleinberg & Tardos (2006).
- 1 2 3 Cormen et al. (2022), Section 22.1.
- ↑ Dinitz, Yefim; Itzhak, Rotem (2017-01-01). "Hybrid Bellman–Ford–Dijkstra algorithm". Journal of Discrete Algorithms. 42: 35–44. doi:10.1016/j.jda.2017.01.001. ISSN 1570-8667.
- ↑ Ford, Lester R. Jr. (August 14, 1956). Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation.
- Bannister, M. J.; Eppstein, D. (2012). "Randomized speedup of the Bellman–Ford algorithm". Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan. pp. 41–47. arXiv:1111.5414. doi:10.1137/1.9781611973020.6.
- \\tilde O(mn^{8/9})</math> time"},"doi":{"wt":"10.1145/3618260.3649614"},"pages":{"wt":"3–14"},"publisher":{"wt":"Association for Computing Machinery"},"title":{"wt":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024"},"year":{"wt":"2024"}},"i":0}}]}'/>Fineman, Jeremy T. (2024). "Single-source shortest paths with negative real weights in Ford, L. R. Jr.; Fulkerson, D. R. (1962). "A shortest chain algorithm". Flows in Networks. Princeton University Press. pp. 130–134.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022) [1990]. Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 0-262-04630-X. Section 22.1: The Bellman–Ford algorithm, pp. 612–616. Problem 22–1, p. 640.
- Sedgewick, Robert (2002). "Section 21.7: Negative Edge Weights". Algorithms in Java (3rd ed.). Addison-Wesley. ISBN 0-201-36121-3. Archived from the original on 2008-05-31. Retrieved 2007-05-28.