The algorithm was first proposed by Alfonso Simbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.
Bellman Ford Algorithm is a Single-Source Shortest Path Algorithm. It means that it is used to find shortest path from source vertex to all other vertices of a directed/undirected weighted graph. It is used over Dijkstra’s Algorithm when we need to deal with negative weights as Dijkstra’s algorithm fails with negative weights but Bellman Ford algorithm works with negative also.
What is edge relaxation
The algorithm is given below. Here V is the number of vertices of the graph, E stores all edges of the graph and S is the source vertex/node.
u is start vertex of the edge (u, v)
v is end vertex of the edge (u, v)
w is the weight/cost of the edge (u, v)
Algorithm
1)Initialize-Single Source(G, S)
2)for i := 1 to |V| — 1 do{ // we relax each edge n-1 times
3)for each edge (u, v) € E do{
4)Relax(u, v, w) } }
5)for each edge (u, v) € E do{
6)if d[v] >d[u] + w(u, v){ // this is the nth cycle
7)Then return False } } // this means there is negative cycle
8)return True
Bellman Ford’s Complexity
Time Complexity
Best Case Complexity
O(E)
Average Case Complexity
O(VE)
Worst Case Complexity
O(VE)
Space Complexity
And, the space complexity is O(V).
Bellman Ford’s Algorithm Applications
1)For calculating shortest paths in routing algorithms
2)For finding the shortest path