Single Source Shortest Path - Bellman Ford Algorithm - Introduction and Code

 Click Me
 
Why to use Bellman Ford Algorithm?
  • We have seen earlier that both BFS and Dijkstra's algorithm can not be used when we have negative cycle in a graph. So, Bellman Ford Algorithm gives us a way to handle negative cycle in a graph. Remember, in any graph, if we have a negative cycle, we can't use any algorithm to find shortest path. Bellman Ford algorithm helps us to detect and notify the negative cycle in a graph, if present any. 
  • In Bellman Ford Algorithm, our focus is gonna be on edges rather than vertices or nodes. To recall, in Dijkstra's Algorithm, our focus was on nodes.
  • The Bellman Ford Algorithm runs for (V-1) times where V is the no. of vertices/nodes in the graph.In each iteration it go es through all edges and tries to find the optimal shortest distance. Why it runs (V-1) times, we will see to it later in this post.
  • If there is a negative cycle present in graph, the Bellman Ford algorithm can detect it in Vth (V is the no. of vertices/nodes in the graph) iteration and not before that. Why? we will also see this later in this post.

Bellman Ford Algorithm [Time Complexity: O(E.V)   Space Complexity: O(V)]
1. Set all node's distance as infinity (Integer.MAX_VALUE) and that of source node as 0. 
2. For i=1 to V-1 (where, V is the no. of vertices/nodes in the graph):
        3. for each edge in the graph (u->v):
                4. if (distance of u) + (weight of edge u->v) is less than (distance of v):
                        5. Update (distance of v) = (distance of u) + (weight of edge u->v)
                        6. Update parent of v as u

// here comes detecting negative cycle in a graph
7. for each edge in the graph (u->v):
        8. if if (distance of u) + (weight of edge u->v) is less than (distance of v): [means if it can update even further]
                    9. Report the user that negative cycle is present in the graph

10. Print all vertex  with distance from source

Why Bellman Ford Algorithm runs (V-1) times and compares all edges everytime?
Let's take an example of a graph with nodes as :

1 <- 2 <-3 <- 4 

Now, we want to find shortest distance from 4 to 1. So it this case, it will process 4->3 then 3->2 and then 2->1 to calculate the distance. Here, you can see it is running 3 times (no. of edges). So, we come to a conclusion that to process the farthest node of the graph from the source node it will take max (V-1) iterations. Hence, Bellman Ford algorithm runs for V-1 iterations.

Why we are able to confirm the existence of a negative cycle only in Vth iteration? 
Note: Here V is no. of vertices/nodes in the graph.

Because as we have seen above that to reach the farthest node from the source it takes max (V-1) iterations. So, in Vth iteration, if we compare edges and distance according to the condition 4 of the algorithm above, we should not get any change if there is not any negative cycle as we have already processed every vertex till now. But if we do get a change, it means a negative cycle is present which is updating the distance according to condition 4 of above algorithm. So, if we encounter any change in distance, in Vth iteration, we immediately report the user about the existence of a negative cycle and exit from code.



import java.util.*;

// A weighted Graph Node
class GraphNode{
    String name;
    // list to store neighbours
    ArrayList<GraphNode> neighbours;
    // hashmap to store edge weight
    HashMap<GraphNode,Integer> weightMap;
    // shortest distance from source node
    int distance;
    //parent node
    GraphNode parent;
    
    
    // constructor
    GraphNode(String name){
        this.name = name;
        this.neighbours = new ArrayList<>();
        this.weightMap = new HashMap<>();
        this.distance = Integer.MAX_VALUE/2;
        this.parent = null;
    }
    
}

public class Main {
    ArrayList<GraphNode> nodesList;
    
    //constructor
    Main(){
        this.nodesList = new ArrayList<>();
    }
    
    // method to find shortest distance from source node to all other nodes
    // Time Complexity: O(V.E)  Space Complexity: O(V)
    public void bellmanFord(GraphNode source){
       // setting distance of source node as zero
        source.distance=0;
        
        // run v-1 times
        for(int i=1;i<this.nodesList.size();i++){
            // for all node's neighbours
            // so going for all nodes first (u)
            for(GraphNode u : this.nodesList){
                // now going for each edge of node (v)
                for(GraphNode v : u.neighbours){
                    if(u.distance==Integer.MAX_VALUE && v.distance==Integer.MAX_VALUE){
                        continue;
                    }
                    else if((u.distance + u.weightMap.get(v))<v.distance){
                        v.distance = u.distance + u.weightMap.get(v);
                        v.parent = u;
                    }
                }
            }
        }
        
        // Vth iteration , here V is no. of vertices/nodes in the graph
        // used to detect negative cycle
        for(GraphNode u : this.nodesList){
            for(GraphNode v : u.neighbours){
                // if at any time the current value gets updated, it means we have a negative cycle
                if((u.distance + u.weightMap.get(v)) < v.distance){
                    System.out.println("A Negative Cycle exists in the given graph, hence can't find SSSP");
                    return;
                }
            }
        }
        
        // printing shortest path for all nodes from the given source node
        for(int i=0;i<this.nodesList.size();i++){
            System.out.println("Printing Shortest path from source node: "+source.name+" to node : "+this.nodesList.get(i).name);
            System.out.print(" Total distance: "+this.nodesList.get(i).distance+" Shortest path: ");
            printPath(this.nodesList.get(i));
            System.out.println();
            System.out.println();
        }
    }
    
     // A helper function to print the path from source node to the given node
    private void printPath(GraphNode node){
        if(node.parent!=null){
            printPath(node.parent);
        }
        System.out.print(node.name+" ");
    }
    
    //a helper function to add directed weighted edge between source and dest node
    private void addDirectedWeightedEdge(int i, int j, int weight){
        GraphNode src = this.nodesList.get(i-1);
        GraphNode dest = this.nodesList.get(j-1);
        src.neighbours.add(dest);
        src.weightMap.put(dest,weight);
    }
    
    public static void main(String[] args) throws Exception {
        Main graph = new Main();
        
        // adding 5 nodes V1-V5 to nodeList
        for(int i=1;i<=5;i++){
            graph.nodesList.add(new GraphNode("V"+i));
        }
        
        // Now adding directed weighted edges between nodes
        // Diagram for the graph used is on the top of post.
        graph.addDirectedWeightedEdge(1,3,6); //Add V1 -> V3 , weight 6
graph.addDirectedWeightedEdge(1,4,6); //Add V1 -> V4 , weight 6
graph.addDirectedWeightedEdge(2,1,3); //Add V2 -> V1 , weight 3
graph.addDirectedWeightedEdge(3,4,2); //Add V3 -> V4 , weight 2
graph.addDirectedWeightedEdge(4,3,1); //Add V4 -> V3 , weight 1
graph.addDirectedWeightedEdge(4,2,1); //Add V4 -> V2 , weight 1
graph.addDirectedWeightedEdge(5,2,4); //Add V5 -> V2 , weight 4
graph.addDirectedWeightedEdge(5,4,2); //Add V5 -> V4 , weight 2
// Now we have added all nodes and directed weighted edges to it, we can now use Bellman Ford algo
System.out.println("Printing Shortest Path from source V5 to all other nodes using Bellman Ford: ");
System.out.println();
graph.bellmanFord(graph.nodesList.get(4));
    }
}


Output:

Printing Shortest Path from source V5 to all other nodes using Bellman Ford: 

Printing Shortest path from source node: V5 to node : V1
 Total distance: 6 Shortest path: V5 V4 V2 V1 

Printing Shortest path from source node: V5 to node : V2
 Total distance: 3 Shortest path: V5 V4 V2 

Printing Shortest path from source node: V5 to node : V3
 Total distance: 3 Shortest path: V5 V4 V3 

Printing Shortest path from source node: V5 to node : V4
 Total distance: 2 Shortest path: V5 V4 

Printing Shortest path from source node: V5 to node : V5
 Total distance: 0 Shortest path: V5


Comments

Post a Comment

Popular posts from this blog

Quick Sort

According to me, it is the easiest and one of the most important and efficient sorting algorithm. Java 7 also uses quicksort for their .sort() method Time Complexity - O(nlogn) Space Complexity - O(n) -> As we are using recursion, it uses the internal stack In quicksort, we chose a pivot element first (in this program, I chose the last element as pivot) All the elements in any array, which are less than the pivot remains to the left of pivot and all the elements which are greater than the pivot element remains to the right of pivot. To do the above, we first chose last element as pivot element, i as (start-1) and j as start In quicksort, we only have to take care of pivot, i and j Now, we compare if a[i]<= pivot element. If yes, we increment i and swap arr[i] and arr[j] After completing one iteration from start to end, we get a pivot element fixed at its right position. Now, we recursively do this for the left subarray and right subarray to the pivot element. QuickS...
Read more

Disjoint Set - Implemented Using Arrays

Image
  What is a Disjoint Set? Well, Wikipedia has the perfect definition -  A disjoint-set data structure (also called a union-find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses, disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The disjoint set has mainly 3 Operations: makeset() -> makes 'n' number of disjoint sets containing single elements find(currentSet) -> returns the representative/parent of currentSet union(set1,set2) -> merges two disjoint sets represented by set1 and set2 into a new disjoint set.  Before going through code, I would recommend watching this video -  https://www.youtube.com/watch?v=wU6udHRIkcc Code: public class Mai...
Read more

Graph Traversal Code - BFS on Graph represented using Adjacency Matrix

Image
  import java.util.*; // A graph Node class GraphNode{     String name;     boolean isVisited;     //index is used to map this node with index of Adjacency Matrix     int index;      GraphNode(String name,int index){         this.name = name;         this.isVisited = false;         this.index = index;     }      } public class Main {          // A List to store the address of all the nodes of the graph     ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();     // An adjacency Matrix to store the details about which nodes are adjacent to each other (basically which two nodes has a edge between them)     int [][] adjacencyMatrix;          // Constructor     Main(ArrayList<GraphNode> nodeList){         this.nod...
Read more