Single Source Shortest Path - DIJKSTRA'S Algorithm - Introduction and Code

 Click Me


Why do we need Dijkstra's Algorithm?
  • We have seen that BFS can only be used to find the shortest path in unweighted graphs. So, for the weighted graphs, Dijkstra comes to our rescue.
  • Dijkstra can be used for all 6 types of graphs.
  • BUT, there is a scenario where DIJKSTRA's ALGORITHM CAN NOT BE USED: when a graph has a NEGATIVE CYCLE. 
  • So a path is called a 'Negative Cycle' if:
    • a) There is a cycle (quite obvious, isn't it ?)
    • b) The Total weight of the cycle should be a negative number.
      • For example - for now, let's consider in the above graph, the weight of edge AD as -6 instead of +6. Now, if we see the path DBAD, it is a cycle and total weight = 1 + 3 - 6 = -2, that is negative weight. So, a negative cycle.
  • So, what is the reason that Dijkstra's Algorithm fails for a negative cycle?
    • For one more time let's consider in the above graph the weight of edge AD as -6 instead of +6.  Now, we know Dijkstra finds the shortest path. If the graph has a negative cycle as explained above, we get the shortest distance in the negative cycle = -2. Here comes the most interesting part. Dijkstra again goes into a negative cycle because it finds the minimum again. see :
      •  -6 + 1 + 3 -6 + 1 = -7 [First three numbers -6, +1 and +3 are from first iteration as explained above].
      • In this way, it keeps on going and finding the shortest distance every time. Any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. Hence, Dijkstra's Algorithm fails for a graph when it has a negative cycle.
  • We can also use Dijkstra to find the shortest distance from a single source to a single destination node. The only thing we need to do in that case is to break out of the loop when we found the shortest path between source and destination node.
  • As BFS can not be used for weighted graphs, hence now both BFS and Dijkstra can not be used when we have a negative cycle in the graph. We will see later how to deal with the negative cycle. For now, let's focus on Dijkstra's Algorithm.
"Dijkstra's Algorithm"
1. Set the distance of each node as Infinite and that of source node as 0 (zero)
2. Put all these distances in a min Heap.
3. while min-heap is not empty:
        4. extract min from min-heap as the current node
        5. for each neighbours of the current node which are still in min heap :
                6. if (current node's distance + weight of the edge connecting the current node to the current neighbour) is less than current neighbour's distance, we update the current neighbour distance and we also update the parent of current neighbour as the current node
                7. Update/refresh the min-heap.


Code: (click on GitHub icon at the top of the page to go to GitHub repo and see a syntax-highlighted code)

import java.util.*;

// A weighted Graph Node
// The GraphNode is implementing Comparable interface because we are going to use minheap(Priority Queue) for dijkstra
// In PriorityQueue all the elements are ordered using their "natural ordering" and we will be supplying GraphNode to priority queue
// Hence, we need to implement comparable interface to determine the "ordering".
class GraphNode implements Comparable<GraphNode>{
    String name;
    ArrayList<GraphNode> neighbours;
    GraphNode parent;
    
    // following is used in Dijkstra's Algo
    int distance;
    // weightmap is used to store weight of edges to adjacent nodes
    HashMap<GraphNode, Integer> weightMap;
    
    // constructor
    GraphNode(String name){
        this.name = name;
        this.neighbours = new ArrayList<>();
        this.parent = null;
        
        // we set distance of each node except source node to Infinity
        // Here setting max value for all nodes, will be changing distance for source node later.
        this.distance = Integer.MAX_VALUE;
        
        this.weightMap = new HashMap<>();
    }
    
    // ONE MORE THING IS REMAINING
    // whenever we use comparable interface, we need to override the compareTo method
    // This is done to provide the comparable interface the knowledge about how to compare two GraphNodes
    // and finally store it in priority queue or minheap as per the ordering determined by this override method.
    @Override
public int compareTo(GraphNode node) {
    // compares the current node's distance (this.distance) with other node's distance in minheap or priority queue (node.distance).
    // if positive no. is returned -> greater
    // if negative is returned -> smaller
    // if zero is returned -> equal
return this.distance - node.distance;
}
    
    
}
public class Main {
    
    // to store all nodes of directed weighted graph
    ArrayList<GraphNode> nodeList;
    
    // constructor
    Main(){
        this.nodeList = new ArrayList<>();
    }
    
    // function to add an edge from i -> j and add a weight 'weight' to the edge
    public void addDirectedWeightedEdge(int i, int j, int weight){
        GraphNode source = this.nodeList.get(i-1);
        GraphNode dest = this.nodeList.get(j-1);
        source.neighbours.add(dest);
        source.weightMap.put(dest,weight);
    }

    // function to find shortest path from source node to every other node using Dijkstra's algorithm.
//Time Complexity: O(v^2), Space Complexity: O(V)
    public void dijkstra(GraphNode source){
        // using minheap to store distance of all nodes
        PriorityQueue<GraphNode> minHeap = new PriorityQueue<>();
        // setting distance of source node as 0
        // Also, we have already set the distance of all other nodes in GraphNode constructor
        source.distance=0;
        // adding all nodes distance to minheap
        minHeap.addAll(this.nodeList);
        
        while(!minHeap.isEmpty()){
            GraphNode currNode = minHeap.poll();
            
            for(GraphNode neighbour : currNode.neighbours){
                // if neighbour is yet to be processed finally
                if(minHeap.contains(neighbour)){
                    
                    // if (source distance + weight of edge to neighbour node) is less than neighbour distance, we update the neighbour distance
                    // and set neighbour's parent to current node
                    if((currNode.distance + currNode.weightMap.get(neighbour)) < neighbour.distance){
                        neighbour.distance = currNode.distance + currNode.weightMap.get(neighbour);
                        neighbour.parent = currNode;
                        
                        // refreshing the minheap as we have updated neighbour details
                        minHeap.remove(neighbour);
                        minHeap.add(neighbour);
                    }
                }
            }
        }
        
        // printing shortest path for all nodes from the given source node
        for(int i=0;i<this.nodeList.size();i++){
            System.out.println("Printing Shortest path from source node: "+source.name+" to node : "+this.nodeList.get(i).name);
            System.out.print(" Total distance: "+this.nodeList.get(i).distance+" Shortest path: ");
            printPath(this.nodeList.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+" ");
    }
    
    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.nodeList.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 Dijkstra algo
System.out.println("Printing Shortest Path from source V5 to all other nodes using Dijkstra: ");
System.out.println();
graph.dijkstra(graph.nodeList.get(4));
        
    }
}


Output:

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

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

Binary Heap - Introduction

Image
#Image Credit - GeeksForGeeks Types of heap: Min Heap - every node is less than or equal to  its children(s) Max Heap - every node is more than or equal to its children(s) Operations on any heap : create insert extract/delete - we can extract/delete only the top node in any heap traverse delete entire heap get size of heap peek top of heap We should prefer implementing binary heap using arrays and not linked list, as during bottom to top heapify, in reaching the bottom rightmost node we take only 0(1) time in case of array but we take 0(n) time in case of linked list because first, we need to level order traverse the binary heap tree to get bottom-most rightmost element.  Heaps are used to efficiently implement:  Prim's Algorithm Heapsort Priority queue
Read more

Divide and Conquer - Introduction

Image
What is Divide and Conquer? Divide and Conquer is an algorithm paradigm in which we break down a given problem into smaller sub-problems of similar type until the sub-problems are small enough to be solved directly. The solution to these sub-problems are then combined to give a solution to the original problem.  Study the diagram below, it will then make more sense about what we do in Divide and Conquer : Where to Apply Divide and Conquer? The Divide and Conquer can be applied to all those problems that show Optimal Substructure property.  So, What is this Optimal Substructure property now? If we can break down a problem into similar sub-problems and the solution of these sub-problems can be used to create the solution of the whole problem, then that problem is said to have the Optimal Substructure property. For eg. : Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2),    In this example, we can see that if we want to find the Fibonacci number at the nth place, we can break this problem in
Read more

Bubble Sort

Time complexity - O(n^2)  || Space Complexity - O(1) Bubble sort is an inplace sorting algorithm, that means we do not any extra space while bubble sorting public class Main {     public static void main(String[] args) throws Exception {         int[] arr={1,4,4,5,6,2,3,90,120,43,0};                  System.out.println("UnSorted Array :");         for(int i=0;i<arr.length;i++){             System.out.print(arr[i]+" ");         }         System.out.println();         // bubble sort         for(int i=0;i<arr.length-1;i++){ // iterates through first to last cell             for(int j=0;j<arr.length-1-i;j++){ // inner loop controls swapping and extent to which swapping is to be performed in array                 if(arr[j]>arr[j+1]){                     int temp = arr[j];                     arr[j]=arr[j+1];                     arr[j+1]=temp;                 }             }             // after each iteration we ge
Read more