Prashant Mishra
Posted on August 1, 2024
Bellman ford algorithm works on directed graph only ( if you want to use it on undirected graph then you will have
to convert the undirected graph into directed graph first)
Bellman ford algorithm is used to find the single source shortest path even when the graph has negative edge weight(in
which case Dijkstra's fails)
Bellman ford also helps us check if the graph(DAG) has negative edge cycle
What needs to be done:
Relaxation of edges:
if(distance[u] + weight < distance[v]){
distance[v] = distance[u] + weight;
}
This above check needs to be done n-1 times where n is the no. of nodes in the graph
Why n-1 time ?
This is because in every iteration we will get the distance of one of the nodes which will satisfy the above check condition, but after n-1 there won't be any reduction in the distance of any node.
Hence in order to check if negative edge cycle is present in the bellman ford algo we do one more round or check(condition above).
If we again find reducing distance value for any node then we can say that the directed graph has cycle with negative edge weight.
//tc : O(n*m) where n is number of vertices in the graph and m is no. of edges in the graph
/*
* edges: vector of vectors which represents the graph
* S: source vertex to start traversing graph with
* V: number of vertices
*/
class Solution {
static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
int distance[] = new int[V];
int infinity = (int)1e8;
Arrays.fill(distance,infinity);// note : 1e8 is nothing but 10 to the power 8 we can't put infinity here can we :)
//distance of source from source is 0
distance[S]=0;
//n-1 or V-1 time check
//tc: O(n*m)
for(int i =0;i<V-1;i++){
for(ArrayList<Integer> edge : edges){
int u = edge.get(0);
int v = edge.get(1);
int weight = edge.get(2);
if(distance[u]!=infinity && distance[u] + weight < distance[v]){
distance[v] = distance[u] + weight;
}
}
}
//one more check to make sure this directed graph does not have any negative edge cycle
//tc: O(m)
for(ArrayList<Integer> edge : edges){
int u = edge.get(0);
int v = edge.get(1);
int weight = edge.get(2);
if(distance[u]!=infinity && distance[u] + weight < distance[v]){
return new int[]{-1}; // this is nothing but array having -1 as value at index 0;
}
}
return distance;
}
}
Posted on August 1, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
