# 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