Single Source Shortest Path using BFS - Introduction and Code

 Click Me
"What is Single Source Shortest Path (SSSP) ?"
  • It is the shortest path from a source node to a destination node / multiple destination nodes.
  • If we use BFS for finding SSSP, we can do this for only unweighted graphs. This is because if we consider a weighted graph for finding SSSP using BFS, the BFS will traverse the graph in a breadth-wise manner. But there might be a path, having less cost that is ignored by BFS.
  • Exception, a case where we can use BFS in a weighted graph too: BFS always has the least number of edges between any two vertices. So if all edges are of the same weight, we can use BFS to find the shortest path.
  • Also. DFS is very inefficient for finding SSSP as we have a tendency to go deep and it might be possible that the target node has been close all this time. The same has been explained here under the heading "BFS VS DFS - When To Use Which Method ?"
  • Algorithm :
    • It is the same as that of BFS except that here we maintain a parentNode property in each graph node. When we traverse from source to destination, we start from the source, add it to queue, mark it as visited, add all unvisited neighbors into the queue and update neighbors' parent property as the current node. 
    • If at any time the current node becomes equal to destination node we know we have reached the destination, so we backtrack to each node's parent starting from the destination node, print all of them, and break out of the loop. It will be clear from the following code :


import java.util.*;

// A graph node with extra attribute parent 
class GraphNode{
    String name;
    ArrayList<GraphNode> neighbours;
    
    // this keeps track of the parent node of the current node (in BFS Traversal)
    GraphNode parent;
    
    // constructor
    GraphNode(String name){
        this.name = name;
        this.neighbours = new ArrayList<>();
        this.parent=null;
    }
}

public class Main {
    // node list of graph
    ArrayList<GraphNode> nodesList;
    
    // Constructor
    Main(){
        this.nodesList = new ArrayList<>();
    }
    
    // function to add an undirected and unweighted edge between nodes at index i and j of nodelist
    public void addUndirectedEdge(int i, int j){
        GraphNode node1 = this.nodesList.get(i);
        GraphNode node2 = this.nodesList.get(j);
        
        node1.neighbours.add(node2);
        node2.neighbours.add(node1);
        
    }
    
    // function to backtrack to parent node when we found shortest path from source to dest node 
    // and print value of all nodes from parent to dest
    public void printPath(GraphNode curr){
        if(curr.parent!=null){
            printPath(curr.parent);
        }
        System.out.print(curr.name+" ");
    }
    
    // function to find the shortest Distane between two nodes using BFS, assuming there is a valid path from src to dest node
    // Time Complexity - O(V+E)   Space Complexity- O(V+E)
    public void shortestDistaneBFS(GraphNode src, GraphNode dest){
        // resetting parent nodes to null so that old values don't interfere with the new iteration. A node might have multiple parents and we choose best path and best parent in each iteration, so we need to clear the parent property of each node.
        for(int i=0;i<this.nodesList.size();i++){
            this.nodesList.get(i).parent=null;
        }
        System.out.println("Printing Shortest Path from "+src.name+"->"+dest.name);
        Queue<GraphNode> q = new LinkedList<>();
        HashSet<GraphNode> visited = new HashSet<>();
        q.add(src);
        
        while(!q.isEmpty()){
            GraphNode curr = q.poll();
            visited.add(curr);
            
            if(curr==dest){
                printPath(dest);
                break;
            }
            
            for(GraphNode neighbour : curr.neighbours){
                if(!visited.contains(neighbour)){
                    if(neighbour.parent==null){
                        // if the parent of neighbour is null, we set its parent to curr node
                        // if the parent of neighbour is not null, we ignore and not update
                        neighbour.parent = curr;
                    }
                    q.add(neighbour);
                }
            }
        }
        
        System.out.println();
        
    }
    
    public static void main(String[] args) throws Exception {
        Main graph = new Main();
        
        // add 10 nodes from v0-v9
        for(int i=0;i<10;i++){
            GraphNode newNode = new GraphNode("V"+i);
            graph.nodesList.add(newNode);
        }
        
        // add undirected and unweighted edge between two nodes
        graph.addUndirectedEdge(0,8);
graph.addUndirectedEdge(8,2);
graph.addUndirectedEdge(8,9);
graph.addUndirectedEdge(2,1);
graph.addUndirectedEdge(9,1);
graph.addUndirectedEdge(2,4);
graph.addUndirectedEdge(1,3);
graph.addUndirectedEdge(1,7);
graph.addUndirectedEdge(3,4);
graph.addUndirectedEdge(3,5);
graph.addUndirectedEdge(7,6);
graph.addUndirectedEdge(5,6);
// assuming there is a valid path between source node and destination node
// calculating shortest distance between source node and destination node
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(5));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(9));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(6));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(7));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(3));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(0));
graph.shortestDistaneBFS(graph.nodesList.get(2),graph.nodesList.get(4));
graph.shortestDistaneBFS(graph.nodesList.get(5),graph.nodesList.get(2));
graph.shortestDistaneBFS(graph.nodesList.get(6),graph.nodesList.get(2));
graph.shortestDistaneBFS(graph.nodesList.get(5),graph.nodesList.get(5));
    }
}

Output :

Printing Shortest Path from V2->V5
V2 V1 V3 V5 
Printing Shortest Path from V2->V9
V2 V8 V9 
Printing Shortest Path from V2->V6
V2 V1 V7 V6 
Printing Shortest Path from V2->V7
V2 V1 V7 
Printing Shortest Path from V2->V3
V2 V1 V3 
Printing Shortest Path from V2->V0
V2 V8 V0 
Printing Shortest Path from V2->V4
V2 V4 
Printing Shortest Path from V5->V2
V5 V3 V1 V2 
Printing Shortest Path from V6->V2
V6 V7 V1 V2 
Printing Shortest Path from V5->V5
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 br...
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     ...
Read more