Content deleted Content added
m Re-flow comments in the BellmanFord function. Without re-flowing some of the lines that contain comments are wrapped around, which reduces readability in standard text + standard width appearance. |
|||
Line 19:
[[File:Bellman-Ford worst-case example.svg|thumb|In this example graph, assuming that A is the source and edges are processed in the worst order, from right to left, it requires the full {{math||''V''|−1}} or 4 iterations for the distance estimates to converge. Conversely, if the edges are processed in the best order, from left to right, the algorithm converges in a single iteration.]]
Like [[Dijkstra's algorithm]], Bellman–Ford proceeds by [[Relaxation (iterative method)|relaxation]], in which approximations to the correct distance are replaced by better ones until they eventually reach the solution.<ref>{{Cite web |title=Bellman-Ford - finding shortest paths with negative weights - Algorithms for Competitive Programming |url=https://cp-algorithms.com/graph/bellman_ford.html |access-date=2025-04-13 |website=cp-algorithms.com}}</ref><ref>{{Cite web |title=Bellman-Ford Algorithm |url=https://www.thealgorists.com/Algo/ShortestPaths/BellmanFord |access-date=2025-04-13 |website=www.thealgorists.com}}</ref> In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path.{{citation needed}}
However, Dijkstra's algorithm uses a [[priority queue]] to [[Greedy algorithm|greedily]] select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this <math>|V|-1</math> times, where <math>|V|</math> is the number of vertices in the graph.{{citation needed}}
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 depend on the order of edges relaxed, but the final answer remains the same.
| |||