Bellman Ford Algorithm | Easy 🚀
Why we need this algo? 🤖
- For a graph without any negative edge and negative cycle, We can use Dijkstra Algorithm to find the shortest path.
- But if a Graph contains negative edge and negative cycle then Dijkstra will fail and we need to Bellman ford algo for the same.
- Alog with that Bellman can help you find if the graph contains negative cycle.
Negative cycle in a graph means any path weight in the graph might result a negative value. for eg : in the below graph path weight = -2-1+2 = -1, hence negative cycle.
Note that if you keep on moving in the cycle path weight will be decreasing again and again.
What is edge relax? 🤕
In the Graph, if you are going to v from u. then simply apply the below condition:
if(dist[u] + weight < dist[v]){
dist[v] = dist[u] + weight;
}dist[u] = distance already taken to reach U node
dist[v] = distance already taken to reach V node (Some else might already visited V)
weight = distance to V from U
So, relaxing an edge means updating the distance for the connected nodes. 😁
How it works?
- if the graph contains N Nodes , we need relax all the edges N-1 times
class Solution {
static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
//Store the distance taken to reach a node
int[] dist = new int[V];
Arrays.fill(dist, (int)(1e8));
//Source will be always 0 , others will be +infinity
dist[S]=0;
//Relax all the edge number of nodes - 1 times
//O(V * E)
for(int i=0; i<V-1; i++){
//relax edges for each iteration
for(ArrayList<Integer> edge : edges){
int node = edge.get(0);
int adjNode = edge.get(1);
int wt = edge.get(2);
//if the distance is +infinity then no need to update distance
if(dist[node]!=(1e8) && dist[node]+wt < dist[adjNode]){
dist[adjNode] = dist[node]+wt;
}
}
}
//if the graph don't contain any negative cycle, then we can't update distance Nth time
for(ArrayList<Integer> edge : edges){
int node = edge.get(0);
int adjNode = edge.get(1);
int wt = edge.get(2);
//if the below condition pass, it means there is a cycle - becausing travelling in a negative cycle will keep on decreasing the distance😥
if(dist[node]!=(1e8) && dist[node]+wt < dist[adjNode]){
int[] temp = {-1};
return temp;
}
}
return dist;
}
}
Why N-1 times ?
🤔 if we try to draw a graph with N nodes, where from source to destination it should take more than N-1 edge. it is impossible until there is a cycle. 🤦♂️
In the above We can reach 3 from 1 with 2 edges, means N-1 edges. We can introduce cycle to increase the edge. But we should avoid cycle to reach the destination.