Тёмный

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

take U forward
Подписаться 700 тыс.
Просмотров 180 тыс.
50% 1

Опубликовано:

 

29 окт 2024

Поделиться:

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 233   
@takeUforward
@takeUforward 2 года назад
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
@harshdasila6680 2 года назад
problem link is not working !
@sanchittripathi1537
@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
@sairam3351 Год назад
understood
@adarshmv261
@adarshmv261 4 месяца назад
Can the same logic be used if this was not having unit weights but having random weights?
@namanjainjain7958
@namanjainjain7958 День назад
Yes
@GurugubelliAjay
@GurugubelliAjay 9 месяцев назад
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
@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
@rohanb9512 2 года назад
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
@rahulprasad3575 2 года назад
Great observation bro
@cr7johnChan
@cr7johnChan Год назад
yes ,do level order traversal with O(N) time complexity
@idontknow8522
@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
@sairam3351 Год назад
it's enough we just maintain array of whether node is visited or not.
@infinityzero2321
@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
@visase2036 2 года назад
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
@MdSarfrazcs 2 года назад
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
@champion5946 Год назад
@@MdSarfrazcs yes
@rakshan3323
@rakshan3323 4 месяца назад
@@MdSarfrazcs Yes, It is because the first distance need not be the minimum distance possible.
@MdSarfrazcs
@MdSarfrazcs 4 месяца назад
@@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
@kartikgarg7541 3 месяца назад
@@MdSarfrazcs Bro really commented 1 year later
@priyanshusrivastava2145
@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]
@anishkarthik4309
@anishkarthik4309 Год назад
I was able to solve this, without even seeing your idea or explanation. Because of your excellent teaching, my intuition is improving.
@niteshsaxena1066
@niteshsaxena1066 4 месяца назад
same here
@bmishra98
@bmishra98 17 дней назад
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
@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
@CS090Srikanth 19 дней назад
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
@divyareddy7622 16 дней назад
its the exact same code for the both the questions right?
@sahelidebnath5085
@sahelidebnath5085 8 месяцев назад
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
@aakashgoswami2356
@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
@keertilata20 Год назад
thank you so much, you cleared my doubt
@ayushmansharma5321
@ayushmansharma5321 Год назад
@sumurthdixit8482
@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
@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
@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.
@Ben10qz
@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
@abheykalia3409 Год назад
we can use dist array as a vis[] substitute since those dist[i] which have values !=INF are already visited
@stith_pragya
@stith_pragya 5 месяцев назад
Understood..............Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@rishabhranjan5162
@rishabhranjan5162 4 месяца назад
This approach is best for weighted edges. For shortest distance we can just maintain a visited array and do dfs.
@cinime
@cinime 2 года назад
Understood! Such a wonderful explanation as always, thank you very much!!
@yasaswinikarumuri9590
@yasaswinikarumuri9590 2 года назад
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
@takeUforward 2 года назад
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
@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; } }
@abrarmojahidrafi4509
@abrarmojahidrafi4509 11 месяцев назад
I think, for Node 3, the adjacency list will be "0, 1, 4"; not "0, 4".
@Maunil2k
@Maunil2k 4 месяца назад
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
@meetverma4812 2 месяца назад
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
@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.
@itsaryanb9316
@itsaryanb9316 2 года назад
can anyone share me the link to this question?? the description link isn't working !
@JaiN-bj1pj
@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
@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.
@RahulYadav-i6f6c
@RahulYadav-i6f6c 11 месяцев назад
@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?
@saisreeramputta7724
@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
@CodeDaily29
@CodeDaily29 3 месяца назад
hey striver, Can you tell me when to use stack or queue. Or should I memorize them for every question?
@AmanSingh-dk4eg
@AmanSingh-dk4eg Год назад
bhaiya transform ho gye 11:24
@_CodeLifeChronicles_
@_CodeLifeChronicles_ 17 дней назад
i am in the 23 rd q from graph series i hope i will complete till the end
@kaichang8186
@kaichang8186 Месяц назад
understood, thanks for the great video
@praveshjain7525
@praveshjain7525 3 месяца назад
Hey, which tool do you use for online teaching? Can you please share the details of your setup?
@elites5967
@elites5967 2 года назад
key observation : This video was recorded over two weekends( explanation on one and coding on the other ).
@parshchoradia9909
@parshchoradia9909 Год назад
Understood SIr!
@amitp277
@amitp277 Год назад
Great explanation
@rishabhagarwal8049
@rishabhagarwal8049 2 года назад
Understood sir, Thank you very much
@rakshitsathyakumar4332
@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
@Moch117
@Moch117 Год назад
What is the difference between this and Dijkstras ?
@UECAshutoshKumar
@UECAshutoshKumar Год назад
Thank you sir 🙏
@adarshmv261
@adarshmv261 4 месяца назад
Can the same logic be used if this was not having unit weights but having random weights?
@DevashishJose
@DevashishJose 8 месяцев назад
understood, Thank you so much.
@abhisheknag1929
@abhisheknag1929 7 месяцев назад
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; }
@muchmunchies43
@muchmunchies43 2 месяца назад
Understood!
@Rieshu-l9i
@Rieshu-l9i 6 месяцев назад
#Striver rocks 🤟👍
@namamiNarayana
@namamiNarayana Год назад
Understood! :) Thank you for your invaluable efforts striver! _/\_ ^^
@hope-jh7bv
@hope-jh7bv 6 месяцев назад
Understood sir.
@KratosProton
@KratosProton 2 года назад
Great explaination
@ritamganguli3476
@ritamganguli3476 2 года назад
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
@user-rf3he9uv5m
@user-rf3he9uv5m Год назад
understood striver.
@chiragPatel22c
@chiragPatel22c Год назад
but striver, to make adjacency list we'll need O(E) space complexity, but gfg has asked for O(N) space complexity.
@Swiftie13498
@Swiftie13498 9 месяцев назад
Understood Bhaiya
@vikasshokeen6044
@vikasshokeen6044 4 месяца назад
Why didn't we apply the Topology search here.?
@anhadorigamichannel9800
@anhadorigamichannel9800 4 месяца назад
why not make a vis array this time it would significantly enhance time complexity
@-VLaharika
@-VLaharika Год назад
Understood 👍
@Learnprogramming-q7f
@Learnprogramming-q7f 5 месяцев назад
Thank you bhaiya
@itsaryanb9316
@itsaryanb9316 2 года назад
Thanks alott for your effort bhaiya❤️❤️❤️
@ganeshmula4508
@ganeshmula4508 10 месяцев назад
understood sir🙇‍♂🙇‍♂🙇‍♂
@gautamsaxena4647
@gautamsaxena4647 5 месяцев назад
understood bhaiya
@AyushKumar-ty4cl
@AyushKumar-ty4cl Год назад
Previous question can also be solve using this method, plain bfs
@imtiyazuddin4827
@imtiyazuddin4827 7 месяцев назад
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
@saikrishna872
@saikrishna872 Год назад
UNDERSTOOD
@evilpollination1916
@evilpollination1916 5 месяцев назад
Understood
@banothutharun2743
@banothutharun2743 3 месяца назад
understood bro
@p_s1dharth
@p_s1dharth 4 месяца назад
understood sir
@suryakiran2970
@suryakiran2970 Год назад
Understood❤
@josephstark5810
@josephstark5810 Год назад
simple level order traversal
@rashiraj454
@rashiraj454 Месяц назад
understood
@10ankurpandey54
@10ankurpandey54 11 месяцев назад
love u bro
@googleit2490
@googleit2490 Год назад
Understood :) Sep'1, 2023 11:53 pm
@The_Shubham_Soni
@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
@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
@anuragprasad6116 9 месяцев назад
same path is being iterated multiple times. it'll give TLE on large test cases
@gaurav4270
@gaurav4270 2 года назад
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
@YeaOhYeahh 2 года назад
hmmm, I agree with u there is no need of dis[u]>dis[v]+1. Did u initialize res array with " -1 " ??
@gaurav4270
@gaurav4270 2 года назад
@@YeaOhYeahh yesss
@shivasai7707
@shivasai7707 Год назад
did you figure out why did it fail ? I'm stuck at the same
@user-le6ts6ci7h
@user-le6ts6ci7h Год назад
Initialize all of them to 0 with source to -1
@manishreddy58
@manishreddy58 4 месяца назад
Why is it not checked for connected components?
@suhaanbhandary4009
@suhaanbhandary4009 Год назад
understood!!
@keertilata20
@keertilata20 2 года назад
you are greattttttt😃
@juniorboy1903
@juniorboy1903 2 года назад
Bhaiya it is recommended that can i watch your old graph video or not
@aryashjain7893
@aryashjain7893 2 года назад
Sari dekhlo , bahut acchi hai sab🙂
@altafmazhar7762
@altafmazhar7762 2 года назад
No it is not necessary
@pranavindore2410
@pranavindore2410 7 месяцев назад
understood 😀
@p38_amankuldeep75
@p38_amankuldeep75 2 года назад
understood❤❤❤❤❤
@valarmorghulis9244
@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
@saumyaagarwal7 Год назад
see his code properly
@lakshsinghania
@lakshsinghania Год назад
was able to get the intuition and coded myself the dfs part without watching the video
@bhaktisharma9681
@bhaktisharma9681 6 месяцев назад
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
@SakshiSingh-hv1oo 5 месяцев назад
same doubt
@harleenkaur7751
@harleenkaur7751 Год назад
understood😊
@geen4562
@geen4562 4 месяца назад
Why no visited array here? what if it had multiple components??
@pavansrinivas4388
@pavansrinivas4388 3 месяца назад
Does the same not work for DAG with non unit weights?
@pavansrinivas4388
@pavansrinivas4388 3 месяца назад
Realized it wont work
@tanujgarg20
@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
@ababhimanyu806 Год назад
toposort is for directed graph(DAG) here its undirected
@paracetamol9116
@paracetamol9116 6 месяцев назад
@@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.
@shivamsethia2967
@shivamsethia2967 Год назад
thanks :)
@durgeshjadhav01
@durgeshjadhav01 4 месяца назад
nice
@jayantgahlot2653
@jayantgahlot2653 Год назад
doubt: can't we do previous que with this logic ?
@moviesflix7082
@moviesflix7082 2 месяца назад
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
@swaraj.nalawade.4634
@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
@justanuhere
@justanuhere 6 месяцев назад
why cant we solve this question using dijkstra and topo sort like in the previous video?
@rayyansyed2998
@rayyansyed2998 Год назад
"understood"
@rishabhnema2479
@rishabhnema2479 3 месяца назад
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
@flying_humans
@flying_humans 2 года назад
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
@takeUforward 2 года назад
Okay okay, you understood na 😅 typos happen!
@anubhavpabby6856
@anubhavpabby6856 2 года назад
Hi striver bhaiya the gfg link is broken.
@harshdasila6680
@harshdasila6680 2 года назад
understoooodooddddd
@hareeshr3979
@hareeshr3979 2 года назад
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
@ashishbisht5359
@ashishbisht5359 2 года назад
here you go -> practice.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1?page=1&sortBy=accuracy&query=page1sortByaccuracy
@sayakghosh5104
@sayakghosh5104 2 года назад
practice.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1?page=1&sortBy=accuracy&query=page1sortByaccuracy
@technologicalvivek7510
@technologicalvivek7510 3 месяца назад
priority queue kyu nhi use hui isme bhaiya?
@anubhavjasoria4335
@anubhavjasoria4335 2 года назад
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
@saseerak8763
@saseerak8763 2 года назад
public int[] shortestPath(int[][] edges,int n,int m ,int src) { // Code here ArrayList adj = new ArrayList(); for(int i=0;i
@googleit2490
@googleit2490 Год назад
Revision I: Easy peasy Sep'6, 2023 10:46 pm
@chitranshjawere4953
@chitranshjawere4953 4 месяца назад
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; } };
@KapilSharma56419
@KapilSharma56419 3 месяца назад
anyone tell can we apply this method to DAG if no then why and if yes then comment the code in reply?
@akshatgosain3831
@akshatgosain3831 Год назад
efficient c++ code: vector adj(n); for(int i=0;i
@manasranjanmahapatra3729
@manasranjanmahapatra3729 2 года назад
UnderStood
@abhisheknag1929
@abhisheknag1929 7 месяцев назад
what if the graph is directed then will the normal bfs work?
@imtiyazuddin4827
@imtiyazuddin4827 7 месяцев назад
i guess it will work as long as all edges have equal weight
@saibunny1253
@saibunny1253 6 месяцев назад
can you tell me what is normal isnt this video using normal bfs
@saibunny1253
@saibunny1253 6 месяцев назад
ok understood you mean without distance array yes it indeed works because it is like level order they go in an order
@abhisheknag1929
@abhisheknag1929 6 месяцев назад
@@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
@utkarshsingh245
@utkarshsingh245 10 месяцев назад
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; }
@saksham-arora
@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; }
Далее
G-29. Word Ladder - I | Shortest Paths
28:07
Просмотров 210 тыс.
ИСТОРИЯ ПРО ШТАНЫ #shorts
00:32
Просмотров 670 тыс.
I Solved 100 LeetCode Problems
13:11
Просмотров 178 тыс.
Programming Languages Tier List 2024
16:18
Просмотров 7 тыс.
G-35. Print Shortest Path - Dijkstra's Algorithm
19:20
Просмотров 210 тыс.
G-30. Word Ladder - 2 | Shortest Paths
25:42
Просмотров 137 тыс.