The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. It can handle negative weight edges, and can detect negative cycles.
How the Algorithm Works
1. Initialize the distance to the source vertex as 0, and all other vertices as infinity.
2. Relax the edges repeatedly: for each edge (u, v) with weight w, if the distance to v can be reduced by going through u, update the distance to v.
3. Repeat step 2 for a total of |V| – 1 times, where |V| is the number of vertices.
4. Check for negative cycles: if the distance to any vertex can still be reduced, then there is a negative cycle.
Pseudocode
function BellmanFord(graph, source):
distance = new array of size |V|, initialized to infinity
distance[source] = 0
for i from 1 to |V| – 1:
for each edge (u, v) with weight w:
if distance[u] + w < distance[v]:
distance[v] = distance[u] + w
for each edge (u, v) with weight w:
if distance[u] + w < distance[v]:
return “Negative cycle detected”
return distance
Example
Suppose we have a graph with vertices A, B, C, and D, and edges with weights as follows:
– A -> B with weight 2
– A -> C with weight 4
– B -> C with weight -1
– C -> D with weight 3
The Bellman-Ford algorithm would compute the shortest distances from A to all other vertices as follows:
– Distance to A: 0
– Distance to B: 2
– Distance to C: 1 (via B)
– Distance to D: 4 (via C)
Time Complexity
The time complexity of the Bellman-Ford algorithm is O(|V| * |E|), where |V| is the number of vertices and |E| is the number of edges.
Space Complexity
The space complexity of the Bellman-Ford algorithm is O(|V|), where |V| is the number of vertices.