G-28. Shortest Path in Undirected Graph with Unit Weights

[@takeUforward]

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

[@harshdasila6680]

problem link is not working !

[@sanchittripathi1537]

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

[@sairam3351]

understood

[@adarshmv261]

Can the same logic be used if this was not having unit weights but having random weights?

[@namanjainjain7958]

Yes

[@GurugubelliAjay]

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

[@yashlakade179]

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

[@rohanb9512]

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]

Great observation bro

[@cr7johnChan]

yes ,do level order traversal with O(N) time complexity

[@idontknow8522]

@@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 ,

[@sairam3351]

it's enough we just maintain array of whether node is visited or not.

[@infinityzero2321]

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.

[@visase2036]

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)

[@MdSarfrazcs]

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

[@champion5946]

@@MdSarfrazcs yes

[@rakshan3323]

@@MdSarfrazcs Yes, It is because the first distance need not be the minimum distance possible.

[@MdSarfrazcs]

@@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 😢

[@kartikgarg7541]

@@MdSarfrazcs Bro really commented 1 year later

[@anishkarthik4309]

I was able to solve this, without even seeing your idea or explanation. Because of your excellent teaching, my intuition is improving.

[@niteshsaxena1066]

same here

[@priyanshusrivastava2145]

just carry a queue and a distance array which is initially marked a s int_max as soon as we comes to a node we will check if 1+dis[node]

[@bmishra98]

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

[@anubhavbhutani8512]

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

[@CS090Srikanth]

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

[@divyareddy7622]

its the exact same code for the both the questions right?

[@ashdaily7640]

why did we use topo sort there then?

[@sahelidebnath5085]

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

[@Ben10qz]

we can use vis array also so that is can skip some as if it reaches again to some other node dist must be greater than previous.

[@abheykalia3409]

we can use dist array as a vis[] substitute since those dist[i] which have values !=INF are already visited

[@aakashgoswami2356]

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

[@keertilata20]

thank you so much, you cleared my doubt

[@ayushmansharma5321]

[@sumurthdixit8482]

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]

why a single dfs call worked here. and why not the standard dfs where we check if the node is visited then only call the dfs in the main function.

[@toontime7663]

@@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.

[@rishabhranjan5162]

This approach is best for weighted edges. For shortest distance we can just maintain a visited array and do dfs.

[@abrarmojahidrafi4509]

I think, for Node 3, the adjacency list will be "0, 1, 4"; not "0, 4".

[@stith_pragya]

Understood..............Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@Maunil2k]

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]

but if we mark the node as visited we cannot visit it again then how can we make the count of minimum distance in the distance array ?

[@princegupta451]

@@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.

[@JaiN-bj1pj]

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

[@muditkhanna8164]

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.

[@cinime]

Understood! Such a wonderful explanation as always, thank you very much!!

[@saisreeramputta7724]

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

[@yasaswinikarumuri9590]

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]

Yes you can! I was doing it for explanation. You can see a note added in the video when I code it. I guess you skipped some portion of video.

[@NituPandelPCECS]

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

[@CodeDaily29]

hey striver, Can you tell me when to use stack or queue. Or should I memorize them for every question?

[@RahulYadav-i6f6c]

@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?

[@rakshitsathyakumar4332]

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

[@abhisheknag1929]

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

[@anhadorigamichannel9800]

why not make a vis array this time it would significantly enhance time complexity

[@chiragPatel22c]

but striver, to make adjacency list we'll need O(E) space complexity, but gfg has asked for O(N) space complexity.

[@utkarshsingh245]

understandable solution so far Down below void bfstraverse(vector adj[], vector &mindistance, int visited[], int nodes){ queue que; que.push({0, 0}); visited[0] = 1; mindistance[0] = 0; while(!que.empty()){ int node = que.front().first; int weight = que.front().second; que.pop(); for(auto it : adj[node]){ if(visited[it] != 1){ visited[it] = 1; mindistance[it] = min(mindistance[it], weight+1); que.push({it, mindistance[it]}); } } } } vector mindistances(vector adj[], int nodes){ vector mindistance(nodes); fill(mindistance.begin(), mindistance.end(), INT_MAX); int visited[nodes] = {0}; bfstraverse(adj, mindistance, visited, nodes); return mindistance; }

[@praveshjain7525]

Hey, which tool do you use for online teaching? Can you please share the details of your setup?

[@itsaryanb9316]

can anyone share me the link to this question?? the description link isn't working !

[@Moch117]

What is the difference between this and Dijkstras ?

[@AmanSingh-dk4eg]

bhaiya transform ho gye 11:24

[@elites5967]

key observation : This video was recorded over two weekends( explanation on one and coding on the other ).

[@_CodeLifeChronicles_]

i am in the 23 rd q from graph series i hope i will complete till the end

[@kaichang8186]

understood, thanks for the great video

[@adarshmv261]

Can the same logic be used if this was not having unit weights but having random weights?

[@amitp277]

Great explanation

[@AyushKumar-ty4cl]

Previous question can also be solve using this method, plain bfs

[@imtiyazuddin4827]

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

[@UECAshutoshKumar]

Thank you sir 🙏

[@The_Shubham_Soni]

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

[@rahulmehndiratta3856]

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

[@anuragprasad6116]

same path is being iterated multiple times. it'll give TLE on large test cases

[@parshchoradia9909]

Understood SIr!

[@DevashishJose]

understood, Thank you so much.

[@rishabhagarwal8049]

Understood sir, Thank you very much

[@namamiNarayana]

Understood! :) Thank you for your invaluable efforts striver! _/\_ ^^

[@jayantgahlot2653]

doubt: can't we do previous que with this logic ?

[@lakshsinghania]

was able to get the intuition and coded myself the dfs part without watching the video

[@rishabhnema2479]

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

[@KratosProton]

Great explaination

[@vikasshokeen6044]

Why didn't we apply the Topology search here.?

[@ritamganguli3476]

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

[@googleit2490]

Understood :) Sep'1, 2023 11:53 pm

[@itsaryanb9316]

Thanks alott for your effort bhaiya❤️❤️❤️

[@Learnprogramming-q7f]

Thank you bhaiya

[@flying_humans]

I think adjacency list is wrong because the adjacent elements of 3 are 0,1,4 but you have only written 0 and 4.

[@takeUforward]

Okay okay, you understood na 😅 typos happen!

[@juniorboy1903]

Bhaiya it is recommended that can i watch your old graph video or not

[@aryashjain7893]

Sari dekhlo , bahut acchi hai sab🙂

[@altafmazhar7762]

No it is not necessary

[@user-rf3he9uv5m]

understood striver.

[@bhaktisharma9681]

Why dont we push node and distance both in the queue as it being done in the explanation, but not while writing code?

[@SakshiSingh-hv1oo]

same doubt

[@hope-jh7bv]

Understood sir.

[@geen4562]

Why no visited array here? what if it had multiple components??

[@chitranshjawere4953]

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

[@manishreddy58]

Why is it not checked for connected components?

[@ganeshmula4508]

understood sir🙇‍♂🙇‍♂🙇‍♂

[@Swiftie13498]

Understood Bhaiya

[@-VLaharika]

Understood 👍

[@gautamsaxena4647]

understood bhaiya

[@keertilata20]

you are greattttttt😃

[@justanuhere]

why cant we solve this question using dijkstra and topo sort like in the previous video?

[@valarmorghulis9244]

Is the queue of pairs needed? like cant we have only nodes inside the queue and get the distance of that node from dist array?

[@saumyaagarwal7]

see his code properly

[@banothutharun2743]

understood bro

[@suhaanbhandary4009]

understood!!

[@Rieshu-l9i]

#Striver rocks 🤟👍

[@swaraj.nalawade.4634]

class Solution { public: vector shortestPath(vector& edges, int N,int M, int src){ vector adj[N]; // no need to consider wt as its 1 for(int i=0; i

[@StoriesFromWeb13]

thank u nice

[@moviesflix7082]

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

[@pranavindore2410]

understood 😀

[@10ankurpandey54]

love u bro

[@p_s1dharth]

understood sir

[@josephstark5810]

simple level order traversal

[@tanujgarg20]

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.?

[@ababhimanyu806]

toposort is for directed graph(DAG) here its undirected

[@paracetamol9116]

@@ababhimanyu806 doesn't matter, can assume weights to be 1 and apply it. We can't apply it cuz it works for acyclic graphs only.

[@suryakiran2970]

Understood❤

[@akshatgosain3831]

efficient c++ code: vector adj(n); for(int i=0;i

[@pavansrinivas4388]

Does the same not work for DAG with non unit weights?

[@pavansrinivas4388]

Realized it wont work

[@shivamsethia2967]

thanks :)

[@p38_amankuldeep75]

understood❤❤❤❤❤

[@tanishkumar6682]

UNDERSTOOD

[@googleit2490]

Revision I: Easy peasy Sep'6, 2023 10:46 pm

[@harleenkaur7751]

understood😊

[@technologicalvivek7510]

priority queue kyu nhi use hui isme bhaiya?

[@durgeshjadhav01]

nice

[@gaurav4270]

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...................

[@YeaOhYeahh]

hmmm, I agree with u there is no need of dis[u]>dis[v]+1. Did u initialize res array with " -1 " ??

[@gaurav4270]

@@YeaOhYeahh yesss

[@shivasai7707]

did you figure out why did it fail ? I'm stuck at the same

[@user-le6ts6ci7h]

Initialize all of them to 0 with source to -1

[@sanamdeepsingh7914]

understood

[@aniketchaudhary5803]

Understood!!!!

[@shashanktripathi2529]

THERE IS NO OPTION OF SUBMITTING THE PROBLEM IN PYTHON LANGAUGE WHY SO?

[@saksham-arora]

Basic level order should work @takeUForward vector shortestPath(vector& edges, int N,int M, int src){ vector level(N, -1); vector ad(N); for(auto x: edges) { ad[x[0]].push_back(x[1]); ad[x[1]].push_back(x[0]); } queue q; q.push(src); level[src] = 0; while(!q.empty()) { int t = q.front(); q.pop(); for(auto x:ad[t]) { if(level[x] == -1) { level[x] = level[t] + 1; q.push(x); } } } return level; }

[@supratimnayek2776]

Understood

[@anubhavpabby6856]

Hi striver bhaiya the gfg link is broken.

[@kushagramishra3026]

"understood"

[@manasranjanmahapatra3729]

UnderStood

[@abhisheknag1929]

what if the graph is directed then will the normal bfs work?

[@imtiyazuddin4827]

i guess it will work as long as all edges have equal weight

[@saibunny1253]

can you tell me what is normal isnt this video using normal bfs

[@saibunny1253]

ok understood you mean without distance array yes it indeed works because it is like level order they go in an order

[@abhisheknag1929]

@@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

[@lokeshnaidu9324]

How is it different from dijsktras algorithms as it also involves relaxation

[@KapilSharma56419]

anyone tell can we apply this method to DAG if no then why and if yes then comment the code in reply?