Shortest path in undirected graph with unit weights

Intuition:

This problem was solved for directed graphs. One way is to convert the undirected graph into a directed one that requires converting every undirected edge between node a and node b to two directed edges:

From node a to node b. (a->b)
From node b to node a. (b->a)

But this approach will require a significant time to convert the undirected graph to a directed graph due to which it is not a preferred way to solve this problem.

Observation:

Since the question is asking for shortest path to every node, let's try using simple BFS traversal starting from source node (node 0) for the given graph:

It can be seen that for a particular level, all the nodes that are present in the queue have the distance from source node 0 equal to the level number. And since a BFS traversal is performed, it ensures that whenever a node is visited for the first time, it is visited by the shortest path (provided all the edges in the graph are of unit weight).

Hence, a simple BFS traversal can be performed and the distances of the nodes can be found based on the level of BFS traversal. Also, if for particular node is visited from two paths, the distance of the shorter path will be considered.

Modification:

In a BFS traversal, a visited array is required to avoid visiting nodes that are already visited. But since a distance array will be used to store the minimum distance of nodes from source node (node 0), having all values initialized as infinity, the distance array itself can be used as a visited array. It ensures that if a node is visited by a distance larger than the distance in the array, then it is already been visited via a shorter path. Hence, the use of visited array can be avoided optimizing the code.

Approach:

Use an adjacency list to represent the graph. Create a distance array initialized to infinity for all nodes. Set the distance of the source node (0) to 0.
Perform BFS traversal starting from the source node (node 0). Use a queue to perform BFS from the source node.
For each node, update the distance of its adjacent nodes if a shorter path is found and push the node in the queue. Update distances to -1 for nodes that remain unreachable.
Return the result stored.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    // Function to perform BFS traversal
    void bfs(int src, vector<int> adj[],
             vector<int> &dist) {
        
        // Distance of source node from itself is zero
        dist[src] = 0; 
        
        // Queue to facilitate BFS traversal
        queue<int> q;
        
        // Adding source node to queue
        q.push(src); 
        
        // Until the queue is empty
        while(!q.empty()) {
            
            // Get the node from queue
            int node = q.front(); 
            q.pop(); 
            
            // Traverse all its neighbors
            for(auto adjNode : adj[node]) {
                
                // If a shorter distance is found
                if(dist[node] + 1 < dist[adjNode]) {
                    
                    // Update the distance
                    dist[adjNode] = 1 + dist[node]; 
                    
                    // Add the node to the queue
                    q.push(adjNode); 
                }
            }
        }
    }
    
public:

    /* Function to get the shortest path 
    for every node from source node 0 */
    vector<int> shortestPath(vector<vector<int>>& edges, 
                             int N, int M){

        // To store the graph
        vector<int> adj[N];
        
        // Add edges to the graph
        for(auto it : edges) {
            int u = it[0]; // first node
            int v = it[1]; // second node
            
            // Add the edge
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        // Distance array to store the shortest paths
        vector <int> dist(N, 1e9);
        
        // Start the BFS traversal from source node
        bfs(0, adj, dist);
        
        /* If a node is unreachable, 
        updating its distance to -1 */
        for(int i = 0; i < N; i++) {
            if (dist[i] == 1e9) 
                dist[i] = -1;
        }
        
        // Return the result
        return dist;
    }
};

int main() {
    
    int N = 9, M = 10;
    vector<vector<int>> edges = {
        {0,1}, {0,3}, {3,4}, 
        {4,5}, {5,6}, {1,2}, 
        {2,6}, {6,7}, {7,8}, {6,8}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine order of 
	letters based on alien dictionary */
    vector<int> ans = sol.shortestPath(edges, N, M);
    
    // Output
    cout << "The shortest distance of every node from source node is:\n";
    for(int i=0; i < N; i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

public class Solution {

    // Function to perform BFS traversal
    private void bfs(int src, List<Integer>[] adj, 
                     int[] dist) {
        
        // Distance of source node from itself is zero
        dist[src] = 0; 
        
        // Queue to facilitate BFS traversal
        Queue<Integer> q = new LinkedList<>();
        
        // Adding source node to queue
        q.add(src); 
        
        // Until the queue is empty
        while (!q.isEmpty()) {
            
            // Get the node from queue
            int node = q.poll(); 
            
            // Traverse all its neighbors
            for (int adjNode : adj[node]) {
                
                // If a shorter distance is found
                if (dist[node] + 1 < dist[adjNode]) {
                    
                    // Update the distance
                    dist[adjNode] = 1 + dist[node]; 
                    
                    // Add the node to the queue
                    q.add(adjNode); 
                }
            }
        }
    }
    
    /* Function to get the shortest path 
    for every node from source node 0 */
    public int[] shortestPath(int[][] edges, int N, int M) {

        // To store the graph
        List<Integer>[] adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // Add edges to the graph
        for (int[] edge : edges) {
            int u = edge[0]; // first node
            int v = edge[1]; // second node
            
            // Add the edge
            adj[u].add(v);
            adj[v].add(u);
        }
        
        // Distance array to store the shortest paths
        int[] dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        // Start the BFS traversal from source node
        bfs(0, adj, dist);
        
        /* If a node is unreachable, 
        updating its distance to -1 */
        for (int i = 0; i < N; i++) {
            if (dist[i] == Integer.MAX_VALUE) 
                dist[i] = -1;
        }
        
        // Return the result
        return dist;
    }

    public static void main(String[] args) {
        
        int N = 9, M = 10;
        int[][] edges = {
            {0, 1}, {0, 3}, {3, 4}, 
            {4, 5}, {5, 6}, {1, 2}, 
            {2, 6}, {6, 7}, {7, 8}, {6, 8}
        };
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to determine shortest paths */
        int[] ans = sol.shortestPath(edges, N, M);
        
        // Output
        System.out.println("The shortest distance of every node from source node is:");
        for (int i = 0; i < N; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
from collections import deque

class Solution:

    # Function to perform BFS traversal
    def bfs(self, src, adj, dist):
        
        # Distance of source node from itself is zero
        dist[src] = 0 
        
        # Queue to facilitate BFS traversal
        q = deque()
        
        # Adding source node to queue
        q.append(src) 
        
        # Until the queue is empty
        while q:
            
            # Get the node from queue
            node = q.popleft()
            
            # Traverse all its neighbors
            for adjNode in adj[node]:
                
                # If a shorter distance is found
                if dist[node] + 1 < dist[adjNode]:
                    
                    # Update the distance
                    dist[adjNode] = 1 + dist[node]
                    
                    # Add the node to the queue
                    q.append(adjNode)
    
    # Function to get the shortest path 
    # for every node from source node 0
    def shortestPath(self, edges, N, M):
        
        # To store the graph
        adj = [[] for _ in range(N)]
        
        # Add edges to the graph
        for edge in edges:
            u = edge[0] # first node
            v = edge[1] # second node
            
            # Add the edge
            adj[u].append(v)
            adj[v].append(u)
        
        # Distance array to store the shortest paths
        dist = [float('inf')] * N
        
        # Start the BFS traversal from source node
        self.bfs(0, adj, dist)
        
        # If a node is unreachable, 
        # updating its distance to -1
        for i in range(N):
            if dist[i] == float('inf'):
                dist[i] = -1
        
        # Return the result
        return dist

# Main function to execute the code
if __name__ == "__main__":
    
    N = 9
    M = 10
    edges = [
        [0, 1], [0, 3], [3, 4], 
        [4, 5], [5, 6], [1, 2], 
        [2, 6], [6, 7], [7, 8], [6, 8]
    ]
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to determine shortest paths
    ans = sol.shortestPath(edges, N, M)
    
    # Output
    print("The shortest distance of every node from source node is:")
    for i in range(N):
        print(ans[i], end=" ")
class Solution {

    // Function to perform BFS traversal
    bfs(src, adj, dist) {
        
        // Distance of source node from itself is zero
        dist[src] = 0; 
        
        // Queue to facilitate BFS traversal
        const q = [];
        
        // Adding source node to queue
        q.push(src); 
        
        // Until the queue is empty
        while (q.length) {
            
            // Get the node from queue
            const node = q.shift();
            
            // Traverse all its neighbors
            adj[node].forEach(adjNode => {
                
                // If a shorter distance is found
                if (dist[node] + 1 < dist[adjNode]) {
                    
                    // Update the distance
                    dist[adjNode] = 1 + dist[node]; 
                    
                    // Add the node to the queue
                    q.push(adjNode); 
                }
            });
        }
    }
    
    /* Function to get the shortest path 
    for every node from source node 0 */
    shortestPath(edges, N, M) {

        // To store the graph
        const adj = Array.from({ length: N }, () => []);
        
        // Add edges to the graph
        edges.forEach(edge => {
            const u = edge[0]; // first node
            const v = edge[1]; // second node
            
            // Add the edge
            adj[u].push(v);
            adj[v].push(u);
        });
        
        // Distance array to store the shortest paths
        const dist = Array(N).fill(Infinity);
        
        // Start the BFS traversal from source node
        this.bfs(0, adj, dist);
        
        // If a node is unreachable, 
        // updating its distance to -1
        for (let i = 0; i < N; i++) {
            if (dist[i] === Infinity) 
                dist[i] = -1;
        }
        
        // Return the result
        return dist;
    }
}

// Main function to execute the code
const main = () => {
    
    const N = 9;
    const M = 10;
    const edges = [
        [0, 1], [0, 3], [3, 4], 
        [4, 5], [5, 6], [1, 2], 
        [2, 6], [6, 7], [7, 8], [6, 8]
    ];
    
    // Creating an instance of Solution class
    const sol = new Solution();
    
    // Function call to determine shortest paths
    const ans = sol.shortestPath(edges, N, M);
    
    // Output
    console.log("The shortest distance of every node from source node is:");
    for (let i = 0; i < N; i++) {
        process.stdout.write(ans[i] + " ");
    }
};

main();

Complexity Analysis:

Time Complexity: O(N+M)

Creating the graph takes O(M) time.
BFS traversal of graph takes O(N+M) time.
Updating distance of unreachable node takes O(N) time.

Space Complexity: O(N+M)

Storing the graph requires O(M) space.
Visited array takes O(N) space.
The queue space taken during BFS traversal will be O(N) in worst case.

Problem List

Shortest path in undirected graph with unit weights

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Observation:

Modification:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code