In this article, we will study the bellman ford algorithm along with its python code. Also, we will study the example and its corresponding output. Lastly, we will know the time complexity and application of bellman ford in the real world.
What is Bellman-Ford Algorithm?
Bellman-Ford algorithm is used to find the shortest path from the source vertex to every vertex in a weighted graph. Unlike Dijkstra's algorithm, the bellman ford algorithm can also find the shortest distance to every vertex in the weighted graph even with the negative edges. The only difference between the Dijkstra algorithm and the bellman ford algorithm is that Dijkstra's algorithm just visits the neighbour vertex in each iteration but the bellman ford algorithm visits each vertex through each edge in every iteration.
Apart from Bellman-Ford Algorithm and Dijkstra's Algorithm, Floyd Warshall Algorithm is also the shortest path algorithm. But Bellman-Ford algorithm is used to compute the shortest path from the single source vertex to all other vertices whereas Floyd-Warshall algorithms compute the shortest path from each node to every other node.
Bellman ford algorithm follows the dynamic programming approach by overestimating the length of the path from the starting vertex to all other vertices. And then it starts relaxing the estimates by discovering the new paths which are shorter than the previous ones. This process is followed by all the vertices for N-1 times for finding the optimized result.
Algorithm
Begin count := 1 maxEdge := a * (a - 1) / 2 //a is number of vertices for all vertices n of the graph, do distance[n] := ∞ pred[n] := ? done distance[source] := 0 eCount := number of edges in the graph create edge list named edgeList while count < a, do for k := 0 to eCount, do if distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k) distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k) pred[edgeList[k].n] := edgeList[k].m done done count := count + 1 for all vertices k in the graph, do if distance[edgeList[k].n] > distance[edgeList[k].m] + (cost[m,n] for edge k), then return true done return false End
1) Initializing the source vertex with distance to itself as 0 and all other vertices as infinity. Creating the array with size N
2) Calculate the shortest distance from the source vertex. Following this process for N-1 times where N is the number of vertices in the graph
For relaxing the path lengths for the vertices for each edge m-n:
if distance[n] > distance[m] + weight of edge mn, then
distance[n] = distance[m] + weight of edge mn
3) Even after minimizing the path lengths for each vertex after N-1 times, if we can still relax the path length where distance[n] > distance[m] + weight of edge mn then we can say that the graph contains the negative edge cycle.
Therefore, the only limitation of the bellman ford algorithm is that it does not work with a graph having a negative edge cycle.
Example:
Consider the following weighted graph
Select the source vertex with path value 0 and all other vertices as infinity.
Visit the neighbouring edge from the source vertex and relax the path length of the neighbouring vertex if the new calculated path length is smaller than the previous path length
This process must be followed N-1 times where N is the total number of vertices. This is because in the worst-case scenario any vertex’s path length can be changed to an even smaller path length for N times.
Therefore after N-1 iterations, we find our new path lengths and we can check if the graph has a negative cycle or not.
Pseudocode
function bellmanFord(G, S) for each vertex N in G distance[N] <- infinite previous[N] <- NULL distance[S] <- 0 for each vertex N in G for each edge (M,N) in G tempDistance <- distance[M] + edge_weight(M, N) if tempDistance < distance[N] distance[N] <- tempDistance previous[N] <- M for each edge (M,N) in G If distance[M] + edge_weight(M, N) < distance[N} Error: Negative Cycle Exists return distance[], previous[]
We maintain the path length of every vertex and store that in an array with a size N where N is the number of vertices. After the algorithm is over we will backtrack from the last vertex to the source vertex to find the path.
Python Code for bellman ford algorithm
class Graph: def __init__(self, vertices): self.M = vertices # Total number of vertices in the graph self.graph = [] # Array of edges # Add edges def add_edge(self, a, b, c): self.graph.append([a, b, c]) # Print the solution def print_solution(self, distance): print("Vertex Distance from Source") for k in range(self.M): print("{0}\t\t{1}".format(k, distance[k])) def bellman_ford(self, src): distance = [float("Inf")] * self.M distance[src] = 0 for _ in range(self.M - 1): for a, b, c in self.graph: if distance[a] != float("Inf") and distance[a] + c < distance[b]: distance[b] = distance[a] + c for a, b, c in self.graph: if distance[a] != float("Inf") and distance[a] + c < distance[b]: print("Graph contains negative weight cycle") return self.print_solution(distance) g = Graph(5) g.add_edge(0, 1, 2) g.add_edge(0, 2, 4) g.add_edge(1, 3, 2) g.add_edge(2, 4, 3) g.add_edge(2, 3, 4) g.add_edge(4, 3, -5) g.bellman_ford(0)
Output
Vertex Distance from Source
0 0
1 2
2 4
3 2
4 7
Time Complexity
The time complexity of the bellman ford algorithm for the best case is O(E) while average-case and worst-case time complexity are O(NE) where N is the number of vertices and E is the total edges to be relaxed. Also, the space complexity of the bellman ford algorithm is O(N) because the size of the array is N.
Applications
- Used for distance-routing protocol helping in routing the data packets on the network
- Used in internet gateway routing protocol
- Used in routing information protocol
Conclusion
In the above article, we studied what is Bellman-Ford algorithm and why we use it. We studied and understood the bellman ford algorithm step by step along with the example. We further learned python code and the corresponding output for finding the distance from the source vertex in a weighted graph. And lastly, we saw the time complexity for applying the algorithm and the applications which we can use in our practical life.
