Bellman-Ford algorithm

(algorithm)

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 ...)
Johnson's algorithm.

See also Dijkstra's algorithm.

Note: After [CLR90, page 532]

Author: PEB

Implementation

The entry in Wikipedia (C, Assembly, and pseudocode) has a proof, too.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 4 March 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "Bellman-Ford algorithm", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 4 March 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bellmanford.html