বেলম্যান ফোর্ড(Bellman-Ford) অ্যালগরিদমঃ

Bellman-Ford algorithm solves the single shortest path problem like BFS and Dijkstra. But if the input graph has negative edge weights, Dijkstra fails.

Motivating Problem: Given a weighted, directed Graph G with source s and weight w, the Bellman-Ford algorithm returns a boolean value whether or not there is a
negative cycle which is reachable from the source. If there is such a cycle,the algorithm indicates that no solution exists. If there is no such cycle , the algorithm produces the shortest path and their weights.


Let's have a look at the following graph:

Dijkstra greedily sets distance[3]=3 first and uses this value to relax distance[4]=distance[3]+weight(3,4)=3+3=6,before setting distance[3]=distance[2]+weight(2,3)=10+(-10)=0. The correct answer is distance[4]=distance[3]+weight(3,4)=0+3=3. So here dijkstra fails.In this case we need Bellman-Ford algorithm.

Implementation: This algorithm is very simple. If the graph has V nodes and E edges, just relax all E edges V-1 time(s)! very simple,isn't it?😛

This is based on the idea that distance[source]=0 and if we relax an edge(source,u) using only one edge from source then distance[u] will get correct value. Hence,f we relax any other neighbors of source using only one edges from source they also will get correct value. In this way if we relax all the vertices sequentially using 1,2,3,4......V-1 edges, the furthest vertices also will get their correct value. Thus if we relax all E edges V-1 time(s) all the vertices will get their correct value.

***If we relax a graph X times,we get the shortest path from source to all other nodes using highest X edges. Whether you will get a shortest path using more than X edges(relaxing X times),it depends on the order of relaxation.

Negative Cycle: This algorithm has one more interesting thing and that is the detection of Negative cycle. After relaxing all the E edges V-1 times the problem should have been solved i.e there is no way that we can relax more than V-1 times. If we can relax any vertex more than V-1 times, it indicates the presence of negative cycle i.e no solution exists.

Sample code:
References:
    1. Introduction to Algorithm by Thomas H. Cormen
    2. Competitive Programming by Steven & Felix Halim
    3. Shafayet's Blog