Problem Statement

Given a Undirected Graph of N vertices form 0 to N-1 and M edges and a 2D integer array edges, where there is a edge from vertex edge[i][0] to vertex edge[i][1] of unit weight.

Find the shortest path from the source to all other nodes in this graph. In this problem statement, we have assumed the source vertex to be 0. If a vertex is unreachable from the source node, then return -1 for that vertex.

Examples

Example 1:

Input: 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]
               ]
Output: 0 1 2 1 2 3 3 4 4

Explanation:
The above output arrays shows the shortest path to all the nodes from the source vertex (0), Dist[0] = 0, Dist[1] = 1, Dist[2] = 2, ... Dist[8] = 4. Where Dist[node] is the shortest path between src and the node. For a node, if the value of Dist[node] = -1, then we conclude that the node is unreachable from the src node.

Example 2:

Input: n = 8, m = 10,
       edges = [
                [1, 0],
                [2, 1],
                [0, 3],
                [3, 7],
                [3, 4],
                [7, 4],
                [7, 6],
                [4, 5],
                [4, 6],
                [6, 5]
               ]
Output: 0 1 2 1 2 3 3 2

Different Approaches

1️⃣ Topological Sort (BFS)

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:

1. 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.
2. Perform BFS traversal starting from the source node (node 0). Use a queue to perform BFS from the source node.
3. 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.
4. Return the result stored.

Code:

#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;
}

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.