Posts Distance from the Source (Bellman-Ford Algorithm)
Post
Cancel

Distance from the Source (Bellman-Ford Algorithm)

Problem Description

Given a weighted, directed and connected graph of V vertices and E edges, Find the shortest distance of all the vertex’s from the source vertex S. Note: If the Graph contains a negative cycle then return an array consisting of only -1.

Your task is to complete the function bellman_ford( ) which takes a number of vertices V and an E-sized list of lists of three integers where the three integers are u,v, and w; denoting there’s an edge from u to v, which has a weight of w and source node S as input parameters and returns a list of integers where the ith integer denotes the distance of an ith node from the source node.

If some node isn’t possible to visit, then its distance should be 100000000(1e8). Also, If the Graph contains a negative cycle then return an array consisting of only -1.

geeksforgeeks

Solution

WilliamFiset YouTube

Tech Dose YouTube

  • This algorithm can help in detecting negative cycles (if that is present, it will not give us the right answer for the shortest path)
  • It works well for Directed Graphs. For undirected graph, we can consider two way edges from (u->v) and (v->u). If that edge of the undirected graph has a -ve value, Bellman algorithm will not work because it will create a negative cycle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    
    static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
        
        //init -> distance[source node] = 0, rest +infinite or more than the max value possible
        int[] distance = new int[V];
        Arrays.fill(distance, 1001); // -1000 ≤ adj[i][j] ≤ 1000
        distance[S] = 0;
        
        //we need N-1 edges if there are N nodes in a connected graph
        for(int i=0; i<V; i++){
            
            //for the current edge, we know that the cost from u->v is w.
            //if the shortest path from source to u is distance[u], the shortest path from u to v will be:
            //distance[u] + w
            //since we are looking for minimum, pick in minimum between:
            //Min(distance[v], distance[u] + w);
            for(int j=0; j<edges.size(); j++){
                
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int w = edges.get(j).get(2);
                
                distance[v] = Math.min(distance[v], distance[u] + w);
                
            }
            
        }
        
        //save the shortest distance after V-1 iterations
        int[] d1 = new int[V];
            for(int i=0; i<d1.length; i++) d1[i] = distance[i];
        
        //if we add another edge, it will definitely form a cycle
        //if the shortest path for any of the destination nodes now decreases, we can say that it must have formed a -ve cycle
        //in that case we can return [-1] as per the problem
        for(int j=0; j<edges.size(); j++){
            
            int u = edges.get(j).get(0);
            int v = edges.get(j).get(1);
            int w = edges.get(j).get(2);
            
            distance[v] = Math.min(distance[v], distance[u] + w);
            
        }
        
        if(hasNegativeCycle(d1, distance)){
            return new int[]{-1};
        }
        
        //if any of the nodes are not reachable, update its distance to 10^8, as per the problem
        for(int i=0; i<d1.length; i++){
            if(d1[i] >= 1001) d1[i] = 100000000;
        }
        
        //return d1, which was calculated after V-1 iterations
        return d1;
        
    }
    
    static boolean hasNegativeCycle(int[] d1, int[] d2){
        
        for(int i=0; i<d1.length; i++){
            if(d2[i] < d1[i]) return true;
        }
        
        return false;
        
    }
    
}

BETTER WAY TO CODE

We can reduce some extra space that we have used -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    
    static int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int S) {
        
        //init -> distance[source node] = 0, rest +infinite or more than the max value possible
        int[] distance = new int[V];
        Arrays.fill(distance, 100000000); // -1000 ≤ adj[i][j] ≤ 1000
        distance[S] = 0;
        
        //we need N-1 edges if there are N nodes in a connected graph
        for(int i=0; i<V; i++){
            
            //for the current edge, we know that the cost from u->v is w.
            //if the shortest path from source to u is distance[u], the shortest path from u to v will be:
            //distance[u] + w
            //since we are looking for minimum, pick in minimum between:
            //Min(distance[v], distance[u] + w);
            for(int j=0; j<edges.size(); j++){
                
                int u = edges.get(j).get(0);
                int v = edges.get(j).get(1);
                int w = edges.get(j).get(2);
                
                distance[v] = Math.min(distance[v], distance[u] + w);
                
            }
            
        }

        //if the cost reduces for any of the nodes for next iteratation (Vth time), there must be a -ve cycle        
        for(int j=0; j<edges.size(); j++){
            
            int u = edges.get(j).get(0);
            int v = edges.get(j).get(1);
            int w = edges.get(j).get(2);
            
            if(distance[u] + w < distance[v]){
                return new int[]{-1};
            }            
            
        }
        
        return distance;
        
    }
    
}
This post is licensed under CC BY 4.0 by the author.