What is Bellman Ford’s Algorithm in Data Structure? | Data Structure Tutorial
Bellman Ford’s Algorithm in Data Structure
In this article, you will learn Bellman Ford’s Algorithm in detail.
It helps in finding the shortest path from a vertex to all other vertices of a weighted graph. It is very similar to Dijkstra’s algorithm but it can also work with graphs in which edges do have a negative weight too.
How can the weights be negative in a real-life situation?
The edge can have negative weight which seems useless at first sight but it explains the phenomena like cash flow, the heat released/absorbed in a chemical reaction, etc. In particular, if there are multiple ways to reach from one chemical to another chemical, each method will have some sub-reactions which involve both heat dissipation and absorption. If the user wants to figure out the set of reactions that have minimum energy, then we can label the heat absorption as negative weights and heat dissipation as positive weights.
Why is a need to be particular about negative weights?
The negative weight cycles are created by the negative weight edges. It means a cycle that will reduce the total path distance which comes back to the same point. Dijkstra’s algorithm is not able to detect that such a cycle can give an incorrect result and the reason behind this is they can go through a negative weight cycle and reduce the path length.
Working on Bellman’s Algorithm
It works by overestimating the length of the path from the initial vertex to all other vertices. It repeatedly relaxes those estimates by figuring out the new paths that are shorter than the previously overestimated paths.
The steps involved in this are:
- Start with the weighted graph.
- Select a starting vertex and assign infinity path values to all other vertices.
- Traverse each edge and relax the distance of the path if they are inaccurate.
- We perform this V times because in the worst case, a vertex’s path length might need to be adjusted again V times.
- Observe how the vertex at the top right corner had its path length adjusted.
- After all the vertices have their path lengths, we check if a negative cycle is present.
Bellman Ford’s Complexity
Time complexity
The best case complexity is O(V), the average case complexity is O(VE), and the worst case complexity is O(VE).
The space complexity is O(V).
Applications of Bellman Ford’s
- Used in calculating shortest paths in routing algorithms
- Used in finding the shortest path
