NIST

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 11 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "Bellman-Ford algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 11 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bellmanford.html