Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
dfs code: //{ Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends // User function Template for C++ class Solution { public: void dfs(int index,vectoradj[],vector&visited,vector&dis) { visited[index]=1; for(auto i:adj[index]) { if(!visited[i]) { dis[i]=min(dis[i],1+dis[index]); dfs(i,adj,visited,dis); } else if(dis[i]>dis[index]+1) {dis[i]=min(dis[i],1+dis[index]); dfs(i,adj,visited,dis); } } } vector shortestPath(vector& edges, int N,int M, int src){ // code here vectoradj[N];vectorvisited(N,0); for(int i=0;i> n >> m; vector edges; for (int i = 0; i < m; ++i) { vector temp; for(int j=0; j>x; temp.push_back(x); } edges.push_back(temp); } int src; cin >> src; Solution obj; vector res = obj.shortestPath(edges, n, m, src); for (auto x : res){ cout
The first time we visit the node , it is our shortest distance since bfs takes 1 unit distance at a time (So no need to compute compare distance ) . vector shortestPath(vector& edges, int N,int M, int src){ vectoradj[N]; for(auto it:edges){ int u=it[0]; int v=it[1]; adj[u].push_back(v); adj[v].push_back(u); } vectordist(N,-1); dist[src]=0; queueq; q.push({src,0}); while(!q.empty()){ int node=q.front().first; int d=q.front().second; q.pop(); for(auto it:adj[node]){ if(dist[it]==-1){ dist[it]=d+1; q.push({it,d+1}); } } } return dist; }
Thanks a lot of these! Just a small change in your code vector shortestPath(vector& edges, int N,int M, int src){ vectoradj[N]; for(auto it:edges){ int u=it[0]; int v=it[1]; adj[u].push_back(v); adj[v].push_back(u); } vectordist(N,-1); dist[src]=0; queueq; q.push(src); while(!q.empty()){ int node=q.front(); q.pop(); for(auto it:adj[node]){ if(dist[it]==-1){ dist[it] = dist[node]+1; q.push(it); } } } return dist; }
Updating the distance of the neighboring nodes is more appropriate for weighted graphs. I think for unweighted graphs the first time when we reach the target node, that should be the shortest distance
@@rahulprasad3575 Its not an observation , BFS do level order traversal , If a node is already visited and try to visit again means that we are currently ahead of that level , going backwards always give bigger distance , so never update visited nodes. ,, Also there is no meaning of taking pair in queue structure ,
if you think of it in a way then this is kind of an unweighted graph in itslef since the distance between each neighbour is 1 so if you do not consider it, wont matter.
Thank you for your immense efforts Striver. Here is one more easier approach inspired from your (01 matrix graph lecture G13) 1. Initialize distance=[-1]*(V) 2. distance[0]=0 // as ''0' is the src node 3. add (0) alone to the "queue" 2. Plain BFS: Take out the node from the queue Update the children's distance from that node : node=q.front() q.pop() for children in adjList[node]: if distance[children]==-1: #Since BFS will give us the sorted shortest distance its jus enough to check if its -1 distance[children]=distance[node]+weight (weight is 1 here) q.append(children) Once the BFS is done return distance if distance [i]==-1, there is no path from src to that node TC:O(V+2E) SC:O(2V)
Hey I have first solve my own via this method , I think the weight of edge is 1 so it's work fine If edges weight vary than this approach didn't work in that case we have to follow standard ways that striver teach
@@rakshan3323 lol 🤣 there was time I was solving a graph problem my own now this is the time where I can't solve a medium tree questions feel pitty for my self 😢
In the explanation, you had put pairs in queue, but in the code you just pushed the node. I have written the code according to your explanation and it works: vector shortestPath(vector& edges, int N,int M, int src){ vector adj[N]; // creating an adjacency list to store a graph // Build the adjacent node list from the given edges for(int i = 0; i < M; i++) { // M is nothing but no.of edges in graph, i.e., edges.size() int u = edges[i][0]; int v = edges[i][1]; adj[u].push_back(v); adj[v].push_back(u); } queue q; // creating a queue to facilitate BFS traversal vector dist(N, 1e9); // creating a 'dist' array initialized all elements with infinity to keep track of shortest distance q.push({src, 0}); // pushing the source node in queue along with the shortest distance to reach there being 0 obviously dist[src] = 0; // mark dist[src] as 0 while(!q.empty()) { int node = q.front().first; // this is the current node int distance = q.front().second; // this is the shortest distance to reach this current node q.pop(); // Traverse neighbours of the current node and update the 'dist' array and push {node, distance} in queue // if a shorter distance is found to reach the neighbour than the existing distance to reach neighbour. for(int neighbour: adj[node]) { if(distance + 1 < dist[neighbour]) { dist[neighbour] = distance + 1; q.push({neighbour, distance+1}); } } } // If a node is unreachable, mark it as -1. for(int i = 0; i < N; i++) { if(dist[i] == 1e9) dist[i] = -1; } return dist; }
we can apply the same thing we are doing in this question to the previous question i.e Shortest Path in Directed Acyclic Graph as well. This is the code. vector adj[N]; // Adjacency list for weighted graph for (int i = 0; i < M; i++) { int u = edges[i][0], v = edges[i][1], weight = edges[i][2]; adj[u].push_back({v, weight}); } vector dist(N, INT_MAX); queue q; q.push(0); dist[0] = 0; while (!q.empty()) { int node = q.front(); q.pop(); // Explore neighbors for (auto it : adj[node]) { int nextNode = it.first; int edgeWeight = it.second; // Relaxation step if (dist[node] + edgeWeight < dist[nextNode]) { dist[nextNode] = dist[node] + edgeWeight; q.push(nextNode); } } } // Replace unreachable nodes' distances with -1 for (auto &it : dist) { if (it == INT_MAX) it = -1; } return dist; }
This wont work for the previuous question due to dissimilar edge weights it would have worked if dag has edge weights as same (1)... Assume we have adjacency list as 0 --> [{1,4},{2,1}] 1 --> [{3,1}] 2 --> [{1,1},{4,6}] 3 --> [{4,1},{5,4}] 4 --> [{6,2},{7,1}] 5 --> [] 6 --> [{5,1}] 7 --> [] Dry run this to understand
Your explanation is insightful. I really love your videos. Thanks for all your dedication for this lovely videos. I have a doubt regarding the repeated checking of vertices in this problem. Since there is a unit distance between vertices, if vertex 3 has been reached previously by vertex 0, why should we check it again? It seems redundant as the distance to vertex 3 will only increase over time, given that the weight is fixed at 1. Instead of repeatedly checking the same vertex, I believe it would be more efficient to maintain a visited array. This would allow us to check if a vertex has already been visited before adding it to the queue, reducing the number of queue operations and subsequently improving the time complexity. While this approach may increase the space complexity by O(n), the overall time complexity will be reduced. I am eager to hear your thoughts on this. I am just bringing by concern. public int[] shortestPath(int[][] edges,int n,int m ,int src) { ArrayList adj = new ArrayList(); int[] dist = new int[n]; Arrays.fill(dist,(int)1e9); boolean[] vis = new boolean[n]; Queue q = new LinkedList(); for(int i= 0;i
If anyone curious about how it can be solved using dfs .Here is the code. private: void findShortestPath(vectoradj[],int V,int node,vector&vis,vector&dist){ vis[node] = 1; for(auto adjNode:adj[node]){ if(dist[adjNode]>dist[node]+1) dist[adjNode] = dist[node]+1; if(!vis[adjNode]){ findShortestPath(adj,V,adjNode,vis,dist); } } vis[node] = 0; return; } public: vector shortestPath(vector& edges, int N,int M, int src){ vectoradj[N]; for(auto edge:edges){ int u = edge[0]; int v = edge[1]; adj[u].push_back(v); adj[v].push_back(u); } vectorvis(N,0); vectordist(N,INT_MAX); dist[src] = 0; findShortestPath(adj,N,src,vis,dist); for(int i=0;i
It can also be solved without using visited array. we only need to do a dfs for a node if it's distance value was minimized in the current dfs call. here is the code void dfs(int s, vector& dist, vector& g) { for(int to : g[s]) { if(dist[to] > dist[s] + 1) { dist[to] = dist[s] + 1; dfs(to, dist, g); } } } vector shortestPath(vector& edges, int N,int M, int src){ vector g(N); for(auto e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); } vector dist(N, 1e9); dist[src] = 0; dfs(src, dist, g); for(int & node : dist) { if(node == 1e9) node = -1; } return dist; }
@@amitrawat8879 becuz after the first dfs call ,all the nodes that are left would be unreachable through the source node and hence we need not to perform dfs for them and in the end we simply assign them -1.
Is there any significance of pushing pair of {Node,dist} into Queue.I mean, is the dist needed to be pushed?Like we can directly fetch the dist from the dist array right?Please do answer this!
@@takeUforward With pair class class pair{ int v, wt; pair(int v, int wt){ this.v = v; this.wt = wt; } } class Solution { public int[] shortestPath(int[][] edges,int n,int m ,int src) { ArrayList adj = new ArrayList(); for(int i = 0; i < n; i++){ adj.add(new ArrayList()); } for(int i = 0 ; i < m; i++){ int a = edges[i][0]; int b = edges[i][1]; adj.get(a).add(b); adj.get(b).add(a); } int dis[] = new int[n]; for(int i = 0 ; i < n; i++){ dis[i] = (int)1e9; } Queue pq = new LinkedList(); pq.add(new pair(src, 0)); dis[src] = 0; while(!pq.isEmpty()){ int first = pq.peek().v; int sec = pq.peek().wt; pq.remove(); for(int it : adj.get(first)){ if(dis[it] > sec+1){ pq.add(new pair(it, sec+1)); dis[it] = sec+1; } } } for(int i = 0 ; i < n; i++){ if(dis[i] == 1e9) dis[i] = -1; } return dis; } }
I have an alternate solution to this. We maintain a visited array and initialize it to 0 except for the source node which is 1 (just like a typical BFS solution). Now, instead of checking for distance(i.e. is the current distance lesser than the previous distance), we check whether the node has been visited or not. If the node is not visited then we simply update the curr_distance + 1 in the distance array for this particular node and push it to the queue. Intuition: If the node hasn't been previously visited then the distance is infinity hence, without checking we can update the distance to dist. + 1 If the node has been previously visited then there is no need to check for distance as it will definitely greater than the current one. This is because BFS explores all the neighbors of the node before moving on to the next node. Code for the same is written below. ``` class Solution { public: vector shortestPath(vector& edges, int N,int M, int src){ vector adj[N]; for(int i=0; i
@@meetverma4812 since the question states that the edges are unit weighted, we only need to reach every node once. BFS traverses by levels and at every next layer the distance would increase by 1. So if I reached a node with a distance of 2 through BFS, next time whenever i reach that node again, the distance would always be greater than what i previously had for that node. However this would only work for unit weighted graph whereas striver's code would work for all cases.
You only have to add the node to the queue, during the first instance, when it's distance is not yet computed. If you are adding it every time it gets updated, it is unnecessary.. code below: public int[] shortestPath(int[][] edges,int n,int m ,int src) { // Code here int[] dist = new int[n]; Arrays.fill(dist, -1); int level = 0; Queue q = new LinkedList(); List adj = new ArrayList(); for(int i=0;i
the queue will push the already pushed although it would impact the distance array as the condition for minimum exist, but can cause high time complexity.
@takeUforward can't we implement Dijkstra algorithum like this? Why we are creating visited and finding the min distance node using priority queue? Why cant we just use this method?
class Solution { public: vector shortestPath(vector& edges, int N,int M, int src){ vector adj[N]; vector dis(N,-1); vector vis(N,-1); queue q; for(int i = 0;i
very similar to level order traversal in binary tree trversal alternative:- class Solution { public: vector shortestPath(vector& edges, int N,int M, int src){ // code here vector adj[N]; for(int i=0;i
Simple BFS will give answer #include using namespace std; vector shortestPath(int n, vector &graph, int src) { // ADJACENCY LIST vector adj[n]; for(auto edge:graph) { int u = edge[0]; int v = edge[1]; adj[u].push_back(v); adj[v].push_back(u); } // Prepare BFS // unordered_map vis; //no need of visited here answer/distance array also works as visited vector answer(n, -1); // Initialize all distances to -1 // Implement BFS queue q; q.push(src); // vis[src] = true; answer[src] = 0; // Distance to source node is 0 while (!q.empty()) { int front = q.front(); q.pop(); for (auto it : adj[front]) { if (answer[it]==-1) { // vis[it] = true; q.push(it); // Update the distance answer[it] = answer[front] + 1; } } } return answer; }
Striver bhiya I am stuck in dp should I do graph after recursion and backtracking also sometimes i forget the approach like the n queen so how to remember them
yes, it can be solved but since in previous question all edges had unequal weights therefore plain bfs would create redundancies as we have to update everytime we get shortest distance
Here is the DFS approach for the same 👇✅ private: void dfs(int node, int vis[], vector &dist, vector adj[]) { vis[node]=1; for(auto i: adj[node]) { if(dist[node]+1 < dist[i]) { dist[i]=dist[node]+1; dfs(i, vis, dist, adj); } } } public: vector shortestPath(vector& edges, int N,int M, int src){ // code here // adjacency list vector adj[N]; for(auto i: edges) { int u=i[0]; int v=i[1]; adj[u].push_back(v); adj[v].push_back(u); } // dfs karo int vis[N]={0}; vector dist(N, 1e9); dist[src]=0; for(int i=0;i
You dont need to perform dfs on all unvisited vertices. Only perform dfs on root to cover all the vertices reachable from root Rest all will be -1 off course
do we acutally need that dis[u]>dis[v]+1 check condition ,since we are doing bfs in bfs nodes at distance are reched first than nodes at distance 2 and so on .... //here v is the source queueq; q.push(v); visited[v]=true; while(q.empty()==false) { int u=q.front(); q.pop(); for(auto it:adj[u]) { if(visited[it]==false) { res[it]=res[u]+ 1; visited[it]=true; q.push(it); } } } this should do the job ryt?? although it giving wrong answer in gfg...................
Wont there be same problem be occuring here as discussed in comment section of previous question i.e there will be too many redundancies in this when using BFS method. Wont it be better if this problem is also solved using toposort and then relax the edges.?
EASY JAVA CODE: class Pair{ int node; int dist; Pair(int node, int dist){ this.node=node; this.dist=dist; } } class Solution { public int[] shortestPath(int[][] edges,int n,int m ,int src) { ArrayList adj = new ArrayList(); for(int i=0; i
Shouldn't we store the distance of the adjacent nodes as pairs and then update the distance? Here is my GFG code: class Solution { public: vector shortestPath(vector& edges, int N,int M, int src){ // code here vectoradj(N); for(int i = 0;iwt+1){ dist[it] = wt+1; q.push({it,dist[it]}); } } } for(int i = 0;i
Hey strivver I can't find the problem link , I tried googling and still can't find it , The one you provided in desc is not working same for the previous video
here you go -> practice.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1?page=1&sortBy=accuracy&query=page1sortByaccuracy
i tried the given problem using dfs and getting very little difference in the output please can someone help me figure this out void dfs(vector&vis,int i,vectoradj[],vector&dis,int d,int par){ vis[i]=1; dis[i]=min(dis[i],d); // cout
Here's the bfs approach : class Solution { public: vector bfstopo(int V, vector adj[]) { // code here queue q; vectorans; vector indeg(V,0); for(int i=0 ; i < V ; i++){ for(auto &adjnode : adj[i])indeg[adjnode.first]++; } for(int i =0 ; i < V; i++){ if (indeg[i]==0)q.push(i); } while(!q.empty()){ auto node =q.front(); ans.push_back(node); q.pop(); for(auto &adjnode :adj[node]){ indeg[adjnode.first]--; if (!indeg[adjnode.first])q.push(adjnode.first); } } return ans; } vector shortestPath(int N,int M, vector& edges){ // code here vector dis(N,1e9); vector adj[N]; for(int i = 0; i< M ; i++){ int a = edges[i][0]; int b = edges[i][1]; int w =edges[i][2]; adj[a].push_back({b,w}); } vector topo = bfstopo(N,adj); //starting point need not mean that it is the starting point of topos // so topos lagana to pura hi padega :) dis[0] = 0; for(int i = 0 ; i < topo.size() ; i++){ int node = topo[i]; if (dis[node] != 1e9) { for (auto &it : adj[node]) { int v = it.first; int wt = it.second; if (dis[node] + wt < dis[v]) { dis[v] = wt + dis[node]; } } } } for(int &i : dis){ if (i==1e9)i=-1; } return dis; } };
@@saibunny1253 by normal bfs I mean the basic bfs algo which we see in books or online where the level of a node tells how much far it is from source node
