DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Shortest Distance from source to all other nodes in the graph where the edge weight is 1 unit

 private void shortestPath(ArrayList<ArrayList<Integer>> adj,int N,int src){
    // we have to find the shortest Path from given source to all the 
    //other nodes in the graph.
    //let's initialize all the distances from the source as infinity.
    int distance[] = new int[N];
    for(int i =0;i<N;i++) distance[i] = Integer.MAX_VALUE;
    // we will put source distance as 0 as its a starting point
    distance[src] = 0;
    //now we will use breadth first search for finding the shortest distance from 
    //source to all other nodes
    Queue<Integer> q = new LinkedList<>();
    q.add(src);
    while(!q.isEmpty()){
        Integer node  = q.remove();
        //getting distance of all the adjacent nodes of current node
        for(Integer i : adj.get(node)){
            if(distance[i]> (distance[node] + 1)){
                distance[i] = distance[node]+1;// since distance of adjacent node will be distance of current node from source + unit distance i.e. 1
                q.add(i);
            }
        }
    }
    for(int i =0;i<N;i++){
        System.out.println("distance of "+i+" from source " +src+" is "+ distance[i]);
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)