DAY 39 - Shortest Path in Undirected graph

Hey everyone! Welcome back to another day of problem-solving. It's day 39, and I'm still going strong on my quest for consistency. Today, we have an interesting problem to tackle. But before we dive in, let's make sure we're all on the same page.

Incase you are unfamiliar with graphs, I suggest reading DAY 32/33 of the same series.

Question:

You are given an Undirected Graph having unit weight, 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.

---

Example:

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

---

Intuition:

I don't think the question needs much explanation here.
From a starting node we need to find the shortest distance for every vertex that we can reach.
In case where we can't reach that vertex we return a -1 for that vertex. We need to output a list of integers with their shortest paths.

Approach:

• To begin, we need to create an adjacency list based on the given edges.
• Next, we'll initialize a distance array called dist to store the shortest distances from the source node to all other nodes. We'll set the initial distances to a large value (1e9), representing infinity, except for the source node which we set to 0.
• To explore the graph and find the shortest paths, we'll employ a Breadth-First Search (BFS) approach. We enqueue the source node at the start.
• In each iteration of the while loop, we'll dequeue a node from the front of the queue. We'll then examine its adjacent nodes by iterating over its adjacency list. For each adjacent node, if the distance to reach it through the current node is shorter than its current recorded distance, we'll update the distance accordingly. We'll also enqueue the adjacent node for further exploration.
• We'll repeat this process until the queue becomes empty, ensuring that we have explored all reachable nodes.
• Once the BFS traversal is complete, we'll create a result vector called ans to store the shortest distances from the source node to all other nodes. We'll initialize all elements of ans to -1.
• Then, we'll iterate over all nodes. For each node, if its distance from the source node is finite (not equal to 1e9), we'll update the corresponding element in ans with the shortest distance.
• Finally, we'll return the ans vector as our solution, containing the shortest distances from the source node to all other nodes.
• By following these steps, we can efficiently find the shortest path from a given source node to all other nodes in the graph.

Code:

vector<int> shortestPath(vector<vector<int>>& edges, int N,int M, int src){
        vector<int> adj[N];
        for(auto it : edges){
            adj[it[0]].push_back(it[1]);
            adj[it[1]].push_back(it[0]);
        }
        vector<int> dist(N,1e9);
        dist[src] = 0;
        queue<int> q;
        q.push(src);

        while(!q.empty()){
            int node  = q.front();
            q.pop();
            for(auto it : adj[node]){
                if(dist[node] +1 < dist[it]){
                    dist[it] = 1  + dist[node];
                    q.push(it);
                }
            }
        }
        vector<int> ans(N,-1);
        for(int i = 0; i < N; i++){
            if(dist[i] != 1e9){
                ans[i] = dist[i];
            }
        }

        return ans;
    }

Complexity Analysis:

• Time: O(N + M)
• Space: O(N + M)

Feel free to let me know if you have any questions or need further clarification. Happy problem-solving!