What is the Bellman-Ford algorithm?

Overview

The Bellman-Ford algorithm is a graph algorithm that computes the shortest distances from a given start vertex to all other vertices. It is similar to Dijkstra’s algorithm, but Bellman-Ford handles negative edge costs and can detect negative cycles.

Basic concept

The algorithm works by overestimating costs from the start vertex to all other vertices and iteratively reducing the cost when new paths are explored. Since V-1 is the maximum length the shortest path could take, it takes at most V-1 iterations to find the smallest cost between start and all other vertices.

Checking for negative cycles

A negative cycle is a cycle in the graph where the sum of the edge costs less than zero. If a negative cycles exist, there can be no shortest path because re-traversing the cycle can lead to increasingly negative values. Hence, if the cost decreases after the previously completed V-1 iterations, a negative cycle must exist.

Pseudocode

Given a graph G with V vertices and edges E:

1. Set cost of all vertices to infinity.
2. Set previous of all vertices to null.
3. Set cost of start vertex to 0.
4. Repeat for the V-1 iterations
1. For all edges (u, v) in G
1. If cost(u) + weight(u, v) < cost(u):
• cost(v) = cost(u) + weight(u, v)
• previous(v) = u

Checking for negative edge cycles:

5. For all edges (u, v) in G

1. If cost(u) + weight(u, v) < cost(v):
• Negative edge cycle found

The following figures show the working of the algorithm with 0 as the start vertex:

Complexities

• Time complexity is O(VE).
• E edges are relaxed V-1 times.
• Space complexity is O(V).
• Arrays of size V are required to store costs and previous vertices.