Тёмный

Shortest Path in Undirected Graph with Unit Weights 

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

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

 

29 окт 2024

Поделиться:

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 152   
@takeUforward
@takeUforward 3 года назад
I will be posting a video every Sunday on the other channel, so bell DABAAAAA dena: ru-vid.com/show-UCvEKHATlVq84hm1jduTYm8g
@gautamsuthar4143
@gautamsuthar4143 3 года назад
10:18 you forgot 1. it is also the adjacency node of 3. Btw, you are amazing. More power to you.
@abhishekvishwakarma9045
@abhishekvishwakarma9045 3 года назад
Watching It at 3:30 AM 😅 before sleep because of your great explanation achi neend aati h phir🔥😁
@youtubeind1850
@youtubeind1850 2 года назад
Mine also before sleeping routine watching these videos at 2x 😅😅
@lovetocode9266
@lovetocode9266 2 года назад
Yr comment motivates me to complete this lecture before sleep, jb mae sooota rahunga aur koi padega that's hit hard
@amitsinghrana6619
@amitsinghrana6619 2 года назад
@@youtubeind1850Isn't 2X too fast? this isn't a video of gate smashers😂
@kabirbanerjee6159
@kabirbanerjee6159 3 года назад
Bhaiya By the time you finished explaining the problem I wrote code by myself and it gave the same output . Thanks you bhaiya.
@prakhargupta5720
@prakhargupta5720 3 года назад
here we can do to reduce time complexity we can use visited array and once the node is visited we wont visit it again, since all edges are of same length. We use BFS to find the minimum one only. So nearest one will always come first.
@naro.tam_
@naro.tam_ 3 года назад
or you will check is it infinity or not?.if not then we can say it is visited. without using visited array
@chiragarora870
@chiragarora870 3 года назад
YES
@naro.tam_
@naro.tam_ 3 года назад
@@chiragarora870 👍
@namanchandra5270
@namanchandra5270 3 года назад
but to do that we have to increase our space complexity but i don't think introducing a visited array would make a much effect on time complexity but space complexity drastically increase.
@udaykiran4202
@udaykiran4202 2 года назад
@@namanchandra5270 even if he uses a visited array the space complexity will still remain O(n);
@prodiptamondal1758
@prodiptamondal1758 3 года назад
Can we say that if we use BFS on an unweighted graph, every distance node will be updated just for once (from infinity to x), And this is the shortest distance for that node. ?
@takeUforward
@takeUforward 3 года назад
Yes because you reach the nodes at levelwise
@lowScales8730
@lowScales8730 2 года назад
Can calculate shortest distance from any node to any node. For any i
@RaviYadav-dz3ir
@RaviYadav-dz3ir 3 года назад
You explain so well that i dont even need to look at the code at end ! I code just by your explanation !
@umangaggarwal2017
@umangaggarwal2017 3 года назад
Amazing explanation 🔥🔥 I can't believe I'm actually able to code it on my own 🙃 You're OP and your teaching style is double OP 🔥🔥
@tulika2863
@tulika2863 3 года назад
hey, i'm not able to find this question on any platform. Will u please tell me where it is available?
@umangaggarwal2017
@umangaggarwal2017 3 года назад
@@tulika2863 yes even I didn't find it on any platform maybe it's a basic one. I just tried it on IDE.
@udayjordan4262
@udayjordan4262 2 года назад
ak bat bataia code to sabhi karla but tuna ya socha ki iisma BFS laga ga aur kasa khud sa logic batana k bad to koi bhi code kar laga
@sriramkrishnamurthy4473
@sriramkrishnamurthy4473 2 года назад
@@udayjordan4262 toh karna lawde , idhar novel likhke kya milega tujhe lassan
@sriramkrishnamurthy4473
@sriramkrishnamurthy4473 2 года назад
@@udayjordan4262 bfs ka hi logic lagega bhai e janabi
@pratikshinde9215
@pratikshinde9215 3 года назад
10:38 you haven't considered 1 as adjacent node of 3, great explanation nonetheless.
@SDE_FACT
@SDE_FACT 3 года назад
Yess👍
@anmolsharma9539
@anmolsharma9539 3 года назад
ya same confusion i think it's just a silly mistake
@TUSHAR-mj1en
@TUSHAR-mj1en 3 года назад
yaa bro
@dannydevito5929
@dannydevito5929 3 года назад
thanks striver for this amazing series... just a suggestion..if you could please add some problem links related to the particular lecture in the description so that we can practice..
@ishaanarora3279
@ishaanarora3279 3 года назад
yes please do this
@charan9237
@charan9237 3 года назад
yes please do it if possible
@destroyer20745
@destroyer20745 3 года назад
much needed
@vedantagarwal22
@vedantagarwal22 3 года назад
yes
@ManishKumar-eb4cu
@ManishKumar-eb4cu 3 года назад
Yes
@ankanbasu7381
@ankanbasu7381 2 года назад
i think we do not need to compare the distance of a node every time we encounter it. the first time we encounter it and change it from INF, is the shortest distance because BFS traversers level wise. so the first time it reaches a node is the shortest distance. so after we change the dist of a node from INF to some value we do not need to check that node anymore btw, thanks Striver bro. these videos help me a lot
@jaydalsaniya6986
@jaydalsaniya6986 2 года назад
Sahi hai
@sanchitraina1346
@sanchitraina1346 2 года назад
considering Unit Weights true observation, otherwise it won't work.
@ankanbasu7381
@ankanbasu7381 2 года назад
@@sanchitraina1346 yes.. the video is about unit weight graphs only. that's why i said it.
@sanchitraina1346
@sanchitraina1346 2 года назад
@@ankanbasu7381 just adding something for newbies
@ankanbasu7381
@ankanbasu7381 2 года назад
@@sanchitraina1346 oh okk.
@raviashwin1157
@raviashwin1157 3 года назад
to skip add click 4:08
@vidhijain4554
@vidhijain4554 3 года назад
Hey!!Thanks for great explanation!!Now I can write code by myself after this level of understanding.
@shreyasvishwakarma8979
@shreyasvishwakarma8979 3 года назад
Bhaiya, what if we want to find the shortest distance b/w any two nodes in the graph. Like not talking specifically about Source Node ..
@sounaksaha1455
@sounaksaha1455 2 года назад
Kya khaake padhate ho yaar.......... Ufff, really maza aa gaya .... beautifully explained.
@letsinevolve6230
@letsinevolve6230 3 года назад
Can we use Pair class instead of dist[]. The Pair class can have 2 properties as: int vertex and int dist_from_source. Then simply have Queue instead of Queue.
@Npanywayme
@Npanywayme 3 года назад
I think it will work.give it a try
@jiosim1377
@jiosim1377 3 года назад
This can also be done with dfs approach too right?
@rahilsanghavi9347
@rahilsanghavi9347 2 года назад
I had a question, can we do this problem like Dijikstra? Use a Priority queue where each element would be a vector containing the weight and node, sorted according to the weight? The relaxation operation is performed as it is.
@sharanpreetchadha5281
@sharanpreetchadha5281 2 года назад
Thanks for the video , would like to know 1 thing , why can't we have a visited array for nodes which have already been visited if we are using BFS because if a node is already visited and we are using BFS then that means the shortest path for that node has been already found out , so we can avoid some repetitions and not check the already visited node again
@pratham654
@pratham654 2 года назад
It is because if we mark the node as visited and after visiting the node one time we will not come to that node again, So after finding the distance to that node from the 1 path we can't say that the distance would be minimum, we have to check from all the paths that's why we didn't maintain the visited array.
@rahulrawat4265
@rahulrawat4265 2 года назад
@@pratham654 Since we are going level wise, we always hit the shortest distance first. So, we can use a visited array in bfs
@arpit743
@arpit743 2 года назад
@@rahulrawat4265 we don't need a visited array for precisely that reason. since visited nodes will not be enqueued untill they have smaller distance from src. This is not possible since BFS gives the min possible distance the first time it visits a node.
@bhaveshkumar6842
@bhaveshkumar6842 2 года назад
Bhai, you're the greatest teacher. I am immensely grateful for your DSA content.
@vaishnavi9755
@vaishnavi9755 2 года назад
Just one question here.. I believe we can apply BFS even when the graph is weighted. Instead of adding 1 in the if statement we can add the weight of the path which will be already stored in adjacency matrix.. I am correct or is there some gap in my thinking?
@princeilu96
@princeilu96 2 года назад
yes
@arpanbanejee5143
@arpanbanejee5143 3 года назад
Can we DFS with a visited array and another array to keep track of the min distance, while returning from DFS we will mark the vis array false for that node, in that way we can visit all possible paths and hence calculate the shortest distance. Pls, correct me if I am wrong. And which approach to follow as a general rule of thumb for these find shortest path kinds of problems and why?
@prashantbisht2219
@prashantbisht2219 3 года назад
It's like detecting cycle in a directed graph right?
@arpanbanejee5143
@arpanbanejee5143 3 года назад
@@prashantbisht2219 Yeh something like that, bt for detecting a cycle we will have to keep another array to keep track of the nodes visited in that dfs call
@life_of_anjali
@life_of_anjali 3 года назад
I'm having a doubt. Since all edges are weighted one, and we are traversing level by level, won't we get the shortest distance the first time you reach a node? Because a node will be reached first through the path having less number of nodes before it in BFS? So, once the distance of a node from the source gets updated from infinity to some other value, it won't be updated again, right? Please correct me if I'm wrong.
@deepanshuyadav4418
@deepanshuyadav4418 3 года назад
Yes, you are absolutely right. In this particular case where edges are weightless (common weights) the nodes once visited are not needed to be considered again. You can use a simple BFS to solve this. But when the edges are weighted you need to consider a node everytime you reach it for if you have found a cheaper path. This is the main difference between BFS and Dijkstra's Algorithm (used in this video).
@saisriangajala8399
@saisriangajala8399 2 года назад
DFs Code : void shortestDistanceDFs(int source, vector graph[], vector &distance) { for (auto &adjNode : graph[source]) { if ((distance[source] + 1) < distance[adjNode]) { distance[adjNode] = distance[source] + 1; shortestDistanceDFs(adjNode, graph, distance); } } } Make sure that the distance[source] is taken as zero, before functional call. This does so many unnecessary calls inorder to get the final shortest distance, BFs is way better than DFs. Just know that this can also be solved with the DFs.
@codeforthought1883
@codeforthought1883 2 года назад
I don't think we need to check the min in BFS because via bfs we will always reach (add them in queue) all nodes in shortest path. Right?
@mukib_khan_
@mukib_khan_ 2 года назад
Right
@tanvisaxena422
@tanvisaxena422 3 года назад
What is the intuition behind using a stack and a queue?
@aakriti1
@aakriti1 2 года назад
Hey, I guess you are trying to ask why we are using queue here and not stack. So basically stacks follow LIFO principle and queue follows FIFO principle. In the diagram given in the video, when you are at 0 node, you push its adjacent elements i.e. 1 and 3 into the queue. What if we push these nodes in a stack? Ans: Then 1 is pushed into the stack then 3 is pushed into the stack. Now in the next iteration, when you'll pop top element from the stack, it will be 3; after processing 3 you will push its adjacent element 4 into the stack. And this process will continue as explained before. But have you observed something once you processed 3 now it was the time to process 1 because we know the fact that BFS (Breadth First Search) visits level-wise but since you used stack we processed 4 instead of 1. That's why we used queue and not the stack. Hope this helps :)
@AnkitJosh
@AnkitJosh 3 года назад
Your lectures are beautiful ❤️
@takeUforward
@takeUforward 3 года назад
Thank you so much!
@programmertik2046
@programmertik2046 2 года назад
Hey where to submit this problem i.e on which platform as links are not provided!!!
@devanshmesson2777
@devanshmesson2777 2 года назад
I think if the graph is directed, then also we can apply this method. Right, Striver?
@gauravkumar6632
@gauravkumar6632 2 года назад
Correction in java code line 28 For(int it:adj.get(node)){
@palakgoyal4231
@palakgoyal4231 2 года назад
distance array should be of n+1 size right ?because if n = 8 we want to go from 0 to 8 that makes the size of array to be 9.Please correct me if I am wrong I have confusion
@sounaksaha1455
@sounaksaha1455 2 года назад
maza aa raha hai... kya padhate ho ... ❤️❤️❤️
@rifathasan6017
@rifathasan6017 3 года назад
How can I print the shortest path to a given node from my given source node?
@cinime
@cinime 2 года назад
Understood! So awesome explanation as always, thank you very much!!
@shivamehta6537
@shivamehta6537 3 года назад
Next level explanation 😍😍
@rahulsaw8838
@rahulsaw8838 2 года назад
Why do we check again and again if the ith distance is already has given some Value For eg if 2nd index is not infinity and given some value then why we are checking for shortest path.if its not infinity then its already the shortest path? These algorithm u've explained will be better for dfs bcoz everytime we are checking multiple times until and unless we get minimal path
@SunnyGupta00
@SunnyGupta00 3 года назад
4:08 skip promotion 🙃
@abhishekpandey239
@abhishekpandey239 3 года назад
Please attach the related problem along with the video
@bhavyakapoor1109
@bhavyakapoor1109 3 года назад
Why can't we use this algorithm for weighted graphs?
@ankishkhandelwal7588
@ankishkhandelwal7588 3 года назад
heY striver Sir Plz visit this If we use vis array [] instead of distance array[] and use pair ; initially push scr < node , distance = 0 > and mark visited we visited every node only one time and add +1 in distance ???
@ankishkhandelwal7588
@ankishkhandelwal7588 3 года назад
anybody see plz reply
@iWontFakeIt
@iWontFakeIt 2 года назад
i think u can do this way but each time u visit a node, mark it unvisited after visiting it since if u don't mark it unvisited it cannot be visited again, and hence u will get the same answer from that question whether it is minimum or not
@GauravKumar-dw2ml
@GauravKumar-dw2ml 2 года назад
Is there any case in which we will put same node in queue more than one time ? #doubt
@princeagrawal7307
@princeagrawal7307 3 года назад
Bhaiya can you also share gfg or leetcode links in description to the problem
@nopecharon
@nopecharon 2 года назад
8:56 this typo doesn't matter but still there should be another node i.e. 1.
@roushanraj8530
@roushanraj8530 3 года назад
But one doubt, for calculating shortest path only one component will be there in graph or it may have multiple components ?? Because you don't used for loop in code that's why asking......., please solve my doubt
@takeUforward
@takeUforward 3 года назад
From source you cannot reach other components so it stays as infinity.
@karanrocks4447
@karanrocks4447 2 года назад
@@takeUforward if graph is connected undirected and unit weight of each edge .. Then can we use this algorithm for answering shortest distance between any two nodes? i.e. Source variable Like in question multiple queries are given Dist bw (u, v) abs (dist[v]-dist[u]) Is it the right way?
@danishparveez849
@danishparveez849 2 года назад
Does the code for c++ will work if there's a cycle in graph?(it isn't checking for visited nodes)
@inclinedscorpio
@inclinedscorpio 2 года назад
you won't push anything in queue if adjacent nodes have length already less. So there is no need of isVisited node.
@arpit743
@arpit743 2 года назад
@@inclinedscorpio Yes precisely, for this exact reason we don't need a visited array since we only enqueue if we find a shorter distance to a node from source in the 2nd time or futher around. However BFS enforces that we find the shortest distance the first time around.
@eshanchourasia287
@eshanchourasia287 2 года назад
will the solution work if we use priority queue in place of queue?
@radhe1335
@radhe1335 3 года назад
Mauj kardi Bhai 😁
@jayadubey_22
@jayadubey_22 3 года назад
Best graph series 🙌
@adarshbadagala
@adarshbadagala 3 года назад
Is it possible to find the shorted distance in the graph without using the distance vector and just by using the visited array like marking the nodes as visited and by incrementing the counter every time we push something into the queue? Just a doubt. Thanks in advance
@igaming_
@igaming_ 2 года назад
Distance vector can't be avoided....and if we use visited array it is consuming extra space instead of that the distance array solves this problem
@arpit743
@arpit743 2 года назад
@@igaming_ Hi it can be avoided if we add a tuple into the queue (node,dist_from_src) and then as we reach each subsequent node we just increment the current distance by 1 and place it as our current neighbhors distance from source node.
@techzone0131
@techzone0131 2 года назад
can we use this approach in undirected weighted graph with the use of bfs.
@hmm7458
@hmm7458 2 года назад
no
@hmm7458
@hmm7458 2 года назад
you have to use dijstras algo
@jiosim1377
@jiosim1377 3 года назад
Amazing explaination! Keep up brother! God bless u with more success!
@engineersaahab6765
@engineersaahab6765 2 года назад
Hello Brother your explanation is too good. But how we can find the minimum distance/node between the source and destination node?? Thanks
@namogh5973
@namogh5973 2 года назад
Just Subtract the the corresponding values of the source and destination nodes in the distance array !
@sayanganguly4806
@sayanganguly4806 2 года назад
practice link- practice.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1
@channelname4394
@channelname4394 2 года назад
Best explanation. understood , hope this channel reaches more people
@JohnWick-kh7ow
@JohnWick-kh7ow 3 года назад
Can we solve it using simple bfs and sorted array?
@prashantbisht2219
@prashantbisht2219 3 года назад
Sir, can you clear my doubt that why can't we use dijskrta algorithm here? Cause we have unit distance edges??
@hmm7458
@hmm7458 2 года назад
yup
@Rahul-gv1mp
@Rahul-gv1mp 3 года назад
What if the undirected graph is disconnected and there are many components in the graph ??
@parthsalat
@parthsalat 2 года назад
Thanks for the wonderful explanation!
@govindrathore1677
@govindrathore1677 3 года назад
If we do this problem with DFS , will be the time complexity will be the same?
@Suhasreddy25
@Suhasreddy25 3 года назад
It should be the same because here we are not keeping any track of visited vertices and visiting them multiple times.
@dhanesh.s
@dhanesh.s 2 года назад
What is the time complexity here?
@arindamkheto2553
@arindamkheto2553 3 года назад
java wale code main 20th line main adj.get(u) ismey u kaha se aaya
@divyanshuchaudhary7328
@divyanshuchaudhary7328 3 года назад
adj.get(node) hoga
@anujagarwal6148
@anujagarwal6148 2 года назад
Why can't this same algorithm be used for Weighted graphs?
@hemantraj2524
@hemantraj2524 3 года назад
best graph series on youtube
@Noone-kl6sc
@Noone-kl6sc 2 года назад
Can I get the problems related to this topic ?
@abhijitroy1958
@abhijitroy1958 2 года назад
quality content with 4k res , what else do i need xd
@divyansh2212
@divyansh2212 2 года назад
wonderful explanation!
@roushanraj8530
@roushanraj8530 3 года назад
Bhaiya toddu explanation 💯💯❤
@KRISHNAKUMAR-yk3tt
@KRISHNAKUMAR-yk3tt 3 года назад
most of the time apka aur mera code match ho jata hai🔥😁
@aasthajha1051
@aasthajha1051 3 года назад
understoooooooooooooooood!!!!!!!!!!!!
@Joyddep
@Joyddep 2 года назад
Thank you!
@arjunkhanna1803
@arjunkhanna1803 2 года назад
Is it dijkstra's algorithm?
@ECEGrishmaKarekar
@ECEGrishmaKarekar 2 года назад
oh , so basically you get the minimum distance the first time yo visit a certain node itself
@auroshisray9140
@auroshisray9140 2 года назад
Great explanation bhaiya
@kshitijpandey9376
@kshitijpandey9376 2 года назад
Awesome Video😊
@shivasundar1998
@shivasundar1998 2 года назад
can someone give me a testcase with it's output?
@rahulsrivastava1040
@rahulsrivastava1040 3 года назад
UNDERSTOOD :)
@chalapathyreddyv8770
@chalapathyreddyv8770 3 года назад
Please add promotion to the last of video
@raju_bugude
@raju_bugude 2 года назад
please provide python code for this
@s.hariharanreddy5439
@s.hariharanreddy5439 2 года назад
Can anyone send me the link to solve this problem?
@Avinashkumar-yq2zr
@Avinashkumar-yq2zr 2 года назад
bro did you find the link to practice??
@runtime379
@runtime379 3 года назад
awsome bhaiya
@manishjaiswal8928
@manishjaiswal8928 2 года назад
nice
@ramvinaykumar589
@ramvinaykumar589 2 года назад
understood
@akhilkumarsingh5041
@akhilkumarsingh5041 3 года назад
I ma getting this prog.java:22: error: cannot find symbol for(int it:adj.get(u)){ ^ symbol: variable u location: class Main 1 error
@kaushikramabhotla4635
@kaushikramabhotla4635 3 года назад
I think It should be "node" instead of "u". try keeping "node".:)
@divyanshuchaudhary7328
@divyanshuchaudhary7328 3 года назад
@@kaushikramabhotla4635 yes
@hhcdghjjgsdrt235
@hhcdghjjgsdrt235 2 года назад
its a game algo
@sayakbasak587
@sayakbasak587 2 года назад
👑👑👑👑👑👑
@shouvikdutta2825
@shouvikdutta2825 3 года назад
a simple bfs, I guess work here???
@_PB03
@_PB03 2 года назад
✅Done
Далее
My 2 Year Journey of Learning C, in 9 minutes
8:42
Просмотров 635 тыс.
DEMONS ARE ATTACKING BRAWL STARS!!!
09:08
Просмотров 15 млн
Bipartite Graph (BFS) | Graph Coloring
25:44
Просмотров 129 тыс.
I Solved 100 LeetCode Problems
13:11
Просмотров 178 тыс.
G-35. Print Shortest Path - Dijkstra's Algorithm
19:20
Просмотров 210 тыс.
20 System Design Concepts Explained in 10 Minutes
11:41
Cycle Detection in Undirected Graph using BFS
25:23
Просмотров 156 тыс.
DEMONS ARE ATTACKING BRAWL STARS!!!
09:08
Просмотров 15 млн