# 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 Tue Feb 12 10:57:42 2019.

Cite this as:

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