Shortest Path in Undirected Graph

Problem

You are given an adjacency list, adj of Undirected Graph having unit weight of the edges, find the shortest path from src to all the vertex and if it is unreachable to reach any vertex, then return -1 for that vertex.

Examples :

Input: adj[][] = [[1, 3], [0, 2], [1, 6], [0, 4], [3, 5], [4, 6], [2, 5, 7, 8], [6, 8], [7, 6]], src=0
Output: [0, 1, 2, 1, 2, 3, 3, 4, 4]

Input: adj[][]= [[3], [3], [], [0, 1]], src=3
Output: [1, 1, -1, 0]

Input: adj[][]= [[], [], [], [4], [3], [], []], src=1
Output: [-1, 0, -1, -1, -1, -1, -1]

Solution

• We are calculating the shortest path for unit weights, but this can be extended to include weights.

• For weighted graphs, the adjacency list stores the weights.

• Instead of using 1, we take the weight from the adjacency list.

• We then compare these weights to find the shorter distances.

• The same algorithms can also be applied to directed graphs.

BFS (Recommended)

Idea: For each node we visit, we add 1 to the current distance and update the node's distance if it's less than the previously calculated distance. We use BFS for this traversal to find the distance.

We start with the source node at a distance of 0 and set all other nodes' distances to Infinity, so we can easily update them with the calculated distances. We find the distance for the next level of nodes and add them to the queue if their distance changes, as these changes can lead to shorter paths for other nodes. This means a node's distance might be recalculated and added to the queue again if a shorter path is found.

Note: We don't need to worry about other connected components that can't be reached from the source node, as they will be marked as -1.

Time - O(V+E)

Space - O(V)

class Solution {
    public int[] shortestPath(ArrayList<ArrayList<Integer>> adj, int src) {
        int n = adj.size();
        int[] dist = new int[n];

        for(int i=0; i<n; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[src] = 0;

        bfs(adj, src, dist);

        for(int i=0; i<n; i++){
            if(dist[i]==Integer.MAX_VALUE){
                dist[i] = -1;
            }
        }
        return dist;
    }

    private void bfs(ArrayList<ArrayList<Integer>> adj, int src, int[] dist){

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(src);
        while(!queue.isEmpty()){
            int vertex = queue.poll();

            for(Integer edgeVertex : adj.get(vertex)){
                if(dist[edgeVertex] > dist[vertex] + 1){
                    dist[edgeVertex] = dist[vertex] + 1;
                    queue.add(edgeVertex);
                }
            }
        }
    }
}

BFS (without Distance comparision) - only for unit weights

Idea: By using BFS traversal, we ensure that we are already moving along the shortest path to any node from the source node. If we encounter a node that has already been visited, it means that the node was first reached by a path that represents the actual shortest path length.

class Solution {
    public int[] shortestPath(ArrayList<ArrayList<Integer>> adj, int src) {
        int n = adj.size();
        int[] dist = new int[n];

        for(int i=0; i<n; i++){
            dist[i] = Integer.MAX_VALUE;
        }

        bfs(adj, src, dist);

        for(int i=0; i<n; i++){
            if(dist[i]==Integer.MAX_VALUE){
                dist[i] = -1;
            }
        }
        return dist;
    }

    private void bfs(ArrayList<ArrayList<Integer>> adj, int src, int[] dist){
        dist[src] = 0;
        int[] visited = new int[adj.size()];
        visited[src] = 1;

        Queue<Integer> queue = new ArrayDeque<>();

        queue.add(src);
        while(!queue.isEmpty()){
            int vertex = queue.poll();

            for(Integer edgeVertex : adj.get(vertex)){
                if(visited[edgeVertex]!=1){
                    dist[edgeVertex] = dist[vertex] + 1;
                    queue.add(edgeVertex);
                    visited[edgeVertex] = 1;
                }
            }
        }  
    }
}

DFS (Not efficient)

We can use DFS to explore all possible paths and find the shortest path from the source. We calculate the distance for each node on every path and keep only the smallest value.

Reason for Inefficiency: If we update a node with the minimum value, we then have to traverse again and update all the connected nodes, repeating the process.

• BFS guarantees shortest distance the first time you reach a node.

• DFS may need to “correct” earlier wrong distances, causing redundant traversals.

• That’s why BFS is the standard choice for unweighted shortest path.

Time - O(V.E)

Space - O(V)

class Solution {
    public int[] shortestPath(ArrayList<ArrayList<Integer>> adj, int src) {
        int n = adj.size();
        int[] dist = new int[n];

        for(int i=0; i<n; i++){
            dist[i] = Integer.MAX_VALUE;
        }

        dist[src] = 0;


        dfs(src, dist, adj);


        for(int i=0; i<n; i++){
            if(dist[i]==Integer.MAX_VALUE){
                dist[i] = -1;
            }
        }

        return dist;
    }

    private void dfs(int vertex, int[] dist, ArrayList<ArrayList<Integer>> adj){

        for(int adjVertex : adj.get(vertex)){
            if(dist[adjVertex] > dist[vertex]+1){
                dist[adjVertex] = dist[vertex]+1;
                dfs(adjVertex, dist, adj);
            }
        }
    }
}