Definition: An efficient algorithm to solve the single-source shortest-path problem. Weights may be negative. The algorithm initializes the distance to the source vertex to 0 and all other vertices to ∞. It then does V-1 passes (V is the number of vertices) over all edges relaxing, or updating, the distance to the destination of each edge. Finally it checks each edge again to detect negative weight cycles, in which case it returns false. The time complexity is O(VE), where E is the number of edges.
Also known as Ford-Bellman.
Aggregate parent (I am a part of or used in ...)
See also Dijkstra's algorithm.
Note: After [CLR90, page 532]
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 4 March 2005.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "Bellman-Ford algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 March 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bellmanford.html