Тёмный

Shortest Path in Directed Acyclic Graph (DAG) 

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

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

 

29 окт 2024

Поделиться:

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист
Посмотреть позже
Комментарии : 277   
@takeUforward
@takeUforward 3 года назад
I will be posting a video every Sunday on the other channel, so bell DABAAAAA dena: ru-vid.com/show-UCvEKHATlVq84hm1jduTYm8g I have commented the intuition in a lot of comments, however you can check this link: stackoverflow.com/questions/37253739/intuition-behind-the-algorithm-to-compute-single-source-shortest-path-for-every The reason of using topo sort is simple, we save a lot of time by starting from the start point, instead of starting from any random point. Since we know via topo sort we get to know the starting point, hence it becomes optimal to use topo sort!
@kumarakashdeep3367
@kumarakashdeep3367 2 года назад
the link to src code is wrong it direct to some other different from the one explained in the video
@swarajkumar9550
@swarajkumar9550 2 года назад
@@kumarakashdeep3367 hey buddy did you get the source code if yes then please send me too
@sriramkrishnamurthy4473
@sriramkrishnamurthy4473 2 года назад
Do u have any sense
@mujtabajafri2803
@mujtabajafri2803 3 года назад
This is a beautiful explanation. I always used to use DP for shortest path in a DAG. But here, you've done the same processing on the topological ordering ! I never imagined of such a beautiful solution.
@devanshmesson2777
@devanshmesson2777 2 года назад
This problem, can be solved through BFS too.But there will be too many redundancies in it. We start from source=0, it relaxes its adjacents, and pushes these adjacent nodes along with their distances into the queue. Then these adjacent nodes will further relax their adjacent nodes and push the relaxed nodes. Consider this graph: first of pair is the adjacent node and second of pair is the edge weight 1->[(2,2), (3,1)] 2->(4,2) 3->(5,1) 5->(4,1) 4->(6,1) Final queue will be like - (first of pair is the node and second of pair is the distance from source to this node) (1,0)(2,2)(3,1)(4,4)(5 2)(6 5)(4 3)(6 4) These all will be popped out when they relax their adjacent nodes. For ex, (1,0) will be popped out before (2,2)(3,1) are pushed into queue and so on. As we can see, there is redundancy, node 4 first came in the queue with a distance of 4 from source, and then again node 4 came with a distance of 3 from the source, which increases time complexity, because, now (4,3) will have to again relax its adjacent nodes to reduce the distances of its adjacent nodes. So, if the pre-requisites of any node(say, cur) are relaxed as minimum as possible before the relaxation of node cur.Then redundancy will never occur. Taking the same example as above, if 1 2 3 5 are relaxed as minimum as possible before the relaxation of node 4. Then redundancy will never occur. The solution to the above observation is Topological sort. If we have Topo sort sequence, then we will take the source node first and relax its adjacent nodes.After that, we take next node in the topo sort, and will do the same. TC - O(N+E) SC-O(N)
@sherlockholmes1605
@sherlockholmes1605 2 года назад
Amazing explanation! Thank you very much :)
@bhavyakapoor1109
@bhavyakapoor1109 2 года назад
Although there will be redundancies in simple BFS method, but the time complexity is still the same i.e O(N+E), also we dont have to find topSort, so isn't BFS better?
@devanshmesson2777
@devanshmesson2777 2 года назад
@@bhavyakapoor1109 I dont think BFS has O(N+E) time complexity, because it is exploring same nodes multiple times.
@vanshsehgal3330
@vanshsehgal3330 2 года назад
Can't we use priority queue?
@harshitsangwan890
@harshitsangwan890 2 года назад
Thanks!
@tannukumari5144
@tannukumari5144 3 года назад
Never thought that i will complete the standard algorithms of graph with so much ease.. thanks striver from ❤️
@priyanshusingh8971
@priyanshusingh8971 3 года назад
outstanding explanation not only for this video ,but whole graph series is very very awesome and free of cost....thanks for this
@vikashgupta3305
@vikashgupta3305 3 года назад
The way he explains is something which shows how passionately he is engaged in programming ❤️, I also wana be like him.
@harshitsangwan890
@harshitsangwan890 2 года назад
Correct me if I am wrong. I think we don't need to find the full topological sort, we can just pass the src as node to the topological sort function, and don't care about the unvisited nodes after we have returned from the function because if they were unvisited even after the end of function that implies they were unreachable from src, so we can remove the loop. Replace //Start for (int i = 0; i < N; i++) if (!vis[i]) findTopoSort(i, vis, st, adj); //End with just "findTopoSort(src vis, st, adj);" This will greatly improve the time complexity for graphs with many nodes unreachable from src.
@devanshmesson2777
@devanshmesson2777 2 года назад
Checking whether the distance of node is infinity or not is not necessary, because as we are coming to this current node (say, cur), the pre-requisite nodes of cur (prerequisites nodes are those whose cur is an adjacent node ) have already relaxed cur (atleast 1 time). So we can remove that INF condition.
@lovetocode
@lovetocode 3 года назад
I think it is one of the best series that I am trying very hard to finish instead of my busy schedules...
@ashirbad29
@ashirbad29 3 года назад
Whoever dislikes this video, I hope your charger only works at certain angles.
@binod3204
@binod3204 3 года назад
wahhhh 🤣🤣
@amitshah817
@amitshah817 3 года назад
Bruh😂
@abhi_azaaad
@abhi_azaaad 3 года назад
ye kaisa shraap hai 🤣
@rajnandini9862
@rajnandini9862 3 года назад
those who have already this special type of charger can relate more...btw its hilarious😂😂
@binod3204
@binod3204 3 года назад
@@rajnandini9862 I can relate it, really painful... and when your charger cable is distorted, it much more than that
@naro.tam_
@naro.tam_ 3 года назад
Thanku striver.I completed this graph series in 8 days and learned so much things.you explained very well.Thankuu again. If you have free time then pls pls pls do make a series on DP...You know there are 3 topics which are most difficult recurssion,graph and dp.I learned recurssion in depth from your live video on codeverse.so i also want to learn DP by u.so pls pls pls if u have time then pls make a series on DP or take live class on codeverse
@taukirkhatri3368
@taukirkhatri3368 2 года назад
For someone getting confused why we are bothering about finding the Topological Sort and the statement "Please check if the distance to the node is not Infinity", Read this comment to understand: 1. Why do we need to find the topological sort? The answer is very simple. For understanding the answer, ask yourself what is the type of the given graph. Yes, it is a DAG. Which means there are no cycles. Right? Of course! That means there are no back edges (an edge from node to itself or its ancestor). Now ask yourself what is a Topological Sort? Yes. It is the ordering of the nodes in the increasing order of the their indegrees. That means all the nodes having less indegree would be on top in this ordering. Now, suppose we want to find a shortest path to a node say 4 in the following topological sort ordering [0, 1, 2, 3, 4, 5, 6]. What is the first thing that comes in your mind? Yes. We need to make sure that before visiting the node 4 all the incoming edges to 4 have been taken into account to find the shortest path to it. This is the property of the topological sort. Isn't it? That's the reason why we should find Topological Sort. 2. Coming to the second point. Which is why do we need to check if the distance to the node in the traversal of the Topological Sort is not infinity. We know that the distance from source node to itself is 0. We also know that the graph is a DAG which do not have any back edge. So, it is obvious that all the nodes before the source node in the topological ordering are unreachable from the source node as there are no back edges. The very first node in the topological ordering which is not having the distance an infinity is the source node itself with the distance of 0. That's the reason why we need to check if the distance is infinity or not. P.S.: In case you need the source that I have used to get the intuition behind this, here is the link to it: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-BNpWnXUhMC4.html&ab_channel=5MinutesEngineering
@krishanpratap3286
@krishanpratap3286 2 года назад
bro isme infinity waala check condition hain woh isliye hain nah ki if there is a node that is unreachable toh usko avoid karne je lie?
@taukirkhatri3368
@taukirkhatri3368 2 года назад
@@krishanpratap3286 Yes! You got the intuition!
@krishanpratap3286
@krishanpratap3286 2 года назад
@@taukirkhatri3368 thanks thanks btw bro which year u at?
@taukirkhatri3368
@taukirkhatri3368 2 года назад
@@krishanpratap3286 Final year of graduation.
@krishanpratap3286
@krishanpratap3286 2 года назад
@@taukirkhatri3368 ayee nice i am in my 4th sem rn nice to talk to you
@samchau8011
@samchau8011 3 года назад
This method is only applicable if the source node is a node with degree 0 and all other nodes are reachable from source node. You can use simple bfs or dfs but the topo sort is used to save time so that you don't have to traverse the same node again as using topo we can maintain a proper sequence of updating the nodes distance from the source!
@bhavyakapoor1109
@bhavyakapoor1109 2 года назад
No, this method can still be used even when other nodes are not reachable from source node, bcz the dist array will remain unchanged and dist of every node from source remains infinity.
@lakshsadhwani855
@lakshsadhwani855 3 года назад
Though I already did graphs, still watching because I love your teaching 😁
@YogeshKumar-px5bd
@YogeshKumar-px5bd 3 года назад
Please provide the question link also so it's easy to check the problem is submitted or not or if we are missing any edge cases.
@rajat_singla
@rajat_singla 2 года назад
Thanks! *Why do we require topological sort instead of normal BFS?* § Unlike unweighted graphs we can't use "only BFS" for weighted graphs. The algorithm fails certain neighbors have dependency on each other. See below graph (blues ones are nodes. Node (0) is directed to node (4) with weight '1' and node (4) is directed to node (1) with weight '1') 0️⃣--'3'-->1️⃣--'2'-->2️⃣ '1'\ '1'/ 4️⃣ □ Now consider neighbors of node (0) = (1), (4). BFS doesn't guarantee which out of (1) or (4) will be processed first (since it depends on the order in which they appear in adjacency list). Lets say (1) is processed first. It updates the distance of node (2) to '5'. □ Now node (4) gets processed and it updates the distance of node (1) to '2'. Ideally, the distance of node (2) should also be updated to '4', but it never happens. Why? because node (1) is already visited and so BFS will not push it in the queue again, and thus it never gets processed again. So, now we have an error in calculating distance for node 2. □ To avoid this error, we have to make sure that all the nodes that (1) depends on, in our case (4), are processed before (1), so that by the time we process (1), we are sure that it will never get updated again. □ How can we do that? By traversing in order of dependencies. That is, for every node all its dependencies should be processed before reaching it. Topological sort provides us with exactly this! □ If we do BFS traversal in order of how they appear in topolgical sorting, we can make sure we don't run into the dependency issues we saw above.
@rajat_singla
@rajat_singla 2 года назад
@Saurabh Patel yes
@Shourya_performs
@Shourya_performs 2 года назад
link to ques? gfg ????
@ayushaneja9076
@ayushaneja9076 2 года назад
the modified bfs discussed in the previous video even works on this example but the only problem is that it takes more turns in queue but the previous video algo works here also.
@rajat_singla
@rajat_singla 2 года назад
@@ayushaneja9076 it might work on this example and some others but there is no guarantee. Try using it for multiple test cases. Very few will pass.
@ayushaneja9076
@ayushaneja9076 2 года назад
@@rajat_singla can you provide any test case Or any kind of link where we can test this?
@prashanth5440
@prashanth5440 2 года назад
Why topological sort? If we found a node with a distance of 7 from src and we updated the other paths in the graph taking 7 into consideration then later we found the distance for the same node from src is 4, in this case, previous paths will be wrong and we have to update them again. what topological sort ensures is that after we update the distance of the source node, since the topological order node will have a node with the maximum number of adjacents at last, we update those adjacents first which prevents the above problem
@bindumahapatra8234
@bindumahapatra8234 2 года назад
Thanks for the great explanation, i successfully coded with your explanation only, no need to check the code, explanation itself was crystal clear.
@rithikdutt1332
@rithikdutt1332 3 года назад
Correct me if I'm wrong, this algorithm finds the shortest distance from unreachable nodes to reachable nodes, right? That is why we use Topo sort correct? But what if the question contains a source node that is different from 0 in this case, like node 2. Should we in that case perform a normal BFS to find the shortest path?
@anmolsharma9539
@anmolsharma9539 3 года назад
did you find the answer now i am getting confused
@rithikdutt1332
@rithikdutt1332 3 года назад
@@anmolsharma9539 this problem can be solved using bfs this technique gives the shortest path from the node with indegree 0 to all other nodes , because we are doing a topo sort at the start. But if the question needs a diff node just proceed with bfs or other shortest path algorithms.
@anmolsharma9539
@anmolsharma9539 3 года назад
@@rithikdutt1332 ok get it thanks 🙏
@nitin5865
@nitin5865 3 года назад
@@rithikdutt1332 Xavier 👍
@AmanKumar-jt9zb
@AmanKumar-jt9zb 3 года назад
@@rithikdutt1332 he has explained that case in the video bro actually then we will print infinity specifically "INF" as in the video u can see the code also in which he has explained this. Now if you will pass 2 as source node the you will get the following output: INF INF 0 6 INF INF here you can see the unreachable node are printed at INF which actually represent the max distance or infinity distance. Hope you got your answer and please clear me if I am wrong!!
@siddhanttyagi6653
@siddhanttyagi6653 3 года назад
bro want the same series for dynamic programming 👏👏
@shreyghugtiyal4118
@shreyghugtiyal4118 3 года назад
and trees also
@suryadiproy7603
@suryadiproy7603 3 года назад
Same here,,Raj da please make video series on dp A request from your college junior
@Adarsh-mn7pl
@Adarsh-mn7pl 2 года назад
aditya verma ki dekh le
@utkarshsingh9968
@utkarshsingh9968 3 года назад
Can we just do DFS without visited and update the distance if it less than the previously updated one??
@yatendra.saraswat
@yatendra.saraswat 3 года назад
if(dis[node]!=inf) is useful in case of disconnected graph am i right? if we dont use it then it will also calculate the distance for unreachable nodes?
@samkr200
@samkr200 3 года назад
No, it's not useful for disconnected graph, it is useful in case of more than one strongly connected components. What I mean to say is, if the source node is there is let's say x. and if the topmost node of the stack (first topo sort node) is y. "If(dis[node]! =inf)", this is just used to check if we are able to reach the y from the x or not. If y is not able to reach from x (as it is a directed graph), then the distance will be kept as infinity itself, we won't change the distance. It's true what you've written, it's just that "disconnected" is not a proper word here.
@chiragarora870
@chiragarora870 3 года назад
@@samkr200 Why do we need to have this check "if(dis[node]!=INF)", can't we do something like "ans[n.first] = min(ans[n.first], ans[curr] + n.second)" As by doing this, we will make sure that we keep the minimum possible distance for visiting each node? And this we will do only for the adjacent nodes of the node popped from the stack?
@eatwithnaima6576
@eatwithnaima6576 3 года назад
why are we not using Dijkstra's algorithm for DAG as well?
@PaAANetiVeeraBadariNarayanaKri
@PaAANetiVeeraBadariNarayanaKri 2 года назад
can't we use the same process which we was used for the undirected unit weight graphs.
@vedantsharma5876
@vedantsharma5876 3 года назад
I think a DFS would be costly, but we could totally use BFS here too!
@siddharthkeshri5649
@siddharthkeshri5649 3 года назад
Great Explanation!!btw code in the Description link is code of detect cycle in undgraph using bfs
@siddharthkeshri5649
@siddharthkeshri5649 3 года назад
Thanks bhaiya ❤️
@divyasingh7480
@divyasingh7480 2 года назад
I have a question. How do we know that the very first element that we are popping out of stack will be s whose dist we initialised as 0, because even when we do topological sort, we don't start with s, we start with 0, so are we assuming here that s=0? Because if top element of stack i.e. topological sort isn't s, then the statement, if dist[node]!=Integer.MAX_VALUE, wont be satisfied
@kamdarfenilnishitbhai6064
@kamdarfenilnishitbhai6064 2 года назад
I have the same doubt
@rohanrastogi1077
@rohanrastogi1077 2 года назад
yes you are right..but we are initializing dist[src]=0 so the nodes before source which are present in the stack will be of no use they will not follow the condition dist[node]!=inf..and simply be popped out from the stack
@divyasingh7480
@divyasingh7480 2 года назад
@@rohanrastogi1077 right makes sense. Thanks for the help!
@rajansahu6450
@rajansahu6450 2 года назад
@@rohanrastogi1077 so basically the topo sort ordering ensures that if there are elements which come before the source , then actually there wont be a path from the source to those vertices (which occurred previously), and hence the distance of those vertices will always remain infinity from the source..right ?
@rohanrastogi1077
@rohanrastogi1077 2 года назад
@@rajansahu6450 yess
@yashs6586
@yashs6586 2 года назад
wanted to ask , as we can see that the src and the top of the stack both are zero , but what if our src was 1 , then what we will do?
@Rahul-xi7hh
@Rahul-xi7hh 2 года назад
The best u can do is apply djikstra algorithm if graph not contains no cycle and no -ve wt
@ranaaditya7960
@ranaaditya7960 2 года назад
please also add the question link in description And u have put the solution of other question in description
@dineshbs6635
@dineshbs6635 2 года назад
Is it possible to somehow extend this algorithm to work with Directed Cyclic graphs with no negative weights?
@roushanraj8530
@roushanraj8530 3 года назад
Bhaiya what if, we want to calculate shortest distance between two given nodes in a graph....., what we can do in that case ?
@shubh13799
@shubh13799 2 года назад
Your Explanation is always exceptional.
@sse6569
@sse6569 2 года назад
The code provided in the description is wrong. Please do check & update it
@TheElevatedGuy
@TheElevatedGuy 2 года назад
Thank you for giving this quality content! But 1 small issue CPP code link is different from the problem. Correct the link for new comers.
@Shourya_performs
@Shourya_performs 2 года назад
link to the ques? anyone
@yashpalrajput4844
@yashpalrajput4844 3 года назад
do we need to have topological sort of whole graph. can'nt we just do it with dfs call from src (for toposort) because nodes in other components are at inf distance anyways.
@malikkonduri3398
@malikkonduri3398 3 года назад
+1
@yashrdoshi
@yashrdoshi 2 года назад
Java Code /* Shortest path in Weighted DAG from a given source node */ import java.util.*; class WDAG{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int v = sc.nextInt(); int e = sc.nextInt(); ArrayList adj = new ArrayList(); for(int i = 0 ;i < v; i++){ adj.add(new ArrayList()); } for(int i = 0 ; i < e; i++){ int u = sc.nextInt(); int vv = sc.nextInt(); int w = sc.nextInt(); ArrayList temp = new ArrayList(); temp.add(vv);temp.add(w); adj.get(u).add(temp); } //Code to print Adj list System.out.println(""); System.out.println("Adjacency List is "); int i = 0; while(i < v ){ for(ArrayList ar : adj.get(i)){ Integer n = ar.get(0), w = ar.get(1); System.out.print(i + " --> ("+ n +" , "+ w +") || "); } System.out.println(""); i++; } System.out.println(""); int src = 0; int[] dis = shorttestPath(v,adj,src); for(int it : dis) if(it != Integer.MAX_VALUE) System.out.print(it+" "); else System.out.print("INF "); System.out.println(""); sc.close(); } public static int[] shorttestPath(int v,ArrayList adj,int src){ boolean[] vis = new boolean[v]; int[] d = new int[v]; Stack st = new Stack(); Arrays.fill(d,Integer.MAX_VALUE); d[src] = 0; for(int i = 0 ; i < v;i++){ if(!vis[i]) dfs(i,vis,st,adj); } while(!st.isEmpty()){ int cur = st.pop(); if(d[cur] != Integer.MAX_VALUE){ for(ArrayList it : adj.get(cur)){ int n = it.get(0), w = it.get(1); if(d[cur] + w < d[n]) d[n] = d[cur] + w; } } } return d; } public static void dfs(int v,boolean[] vis,Stack st, ArrayList adj){ vis[v] = true; for(ArrayList it : adj.get(v)){ int node = it.get(0); if(!vis[node]) dfs(node,vis,st,adj); } st.add(v); } }
@syamsreemanojreddy750
@syamsreemanojreddy750 3 года назад
what is the intuiton behind doing Topo sort before finding the shortest path
@sukritinarang5016
@sukritinarang5016 2 года назад
The video is great!! PS-The code link for CPP is mistaken .
@EverythingaboutTechPro
@EverythingaboutTechPro 3 года назад
Correct me if i am wrong . This is DP . right ? (The distance array stores min distance till node i ).
@shreyghugtiyal4118
@shreyghugtiyal4118 3 года назад
amazing explanation bhaiya please make a playlist on trees and dp aswell.
@yuvraj2038
@yuvraj2038 3 года назад
Dijkstra will work here right? Why are we using topo sort then?
@jaydalsaniya6986
@jaydalsaniya6986 2 года назад
@Shubam Gopal Vyas That's not correct, there are some test cases where overhead still remains as it is. And here striver has take the test case where overhead is not seen. See this graph : each edge u->v is denoted like this [ u , v , wt ] Graph[][] : [ 0 , 1 , 1 ] [ 1 , 2 , 3 ] [ 1 , 3 , 5 ] [ 1 , 4 , 4 ] [ 0 , 3 , 20 ] [ 0 , 4 , 30 ]
@cinime
@cinime 2 года назад
Understood! Amazing explanation as always, thank you very much!!
@himanshusemwal8105
@himanshusemwal8105 2 года назад
but what if dag is cyclic i mean u dont get topo sort in cyclic dag??? back to bfs dfs??
@tejendra.pratap
@tejendra.pratap 3 года назад
What if in this example , the source node is 4 and the distination is 3, then this algorithm will not work i guess. Should we pop the nodes from the stack until we have reached the source node? Thanks
@muskankalra2516
@muskankalra2516 3 года назад
Yeah, we will pop the nodes until we reach the source node(and those nodes which are unreachable from source will be INF) and the algorithm will then compute the distance from the source node to all the reachable nodes from it.
@kartikeyagupta6322
@kartikeyagupta6322 3 года назад
What is the purpose of using topological sort in this question
@takeUforward
@takeUforward 3 года назад
I have answered in the other comments as well. Please check them out, or you can check this article: stackoverflow.com/questions/37253739/intuition-behind-the-algorithm-to-compute-single-source-shortest-path-for-every
@kartikeyagupta6322
@kartikeyagupta6322 3 года назад
@@takeUforward Thank you
@vaishnavigour5777
@vaishnavigour5777 2 года назад
The java code link given in the the video description is for another question ,Pls do update it.....btw This series is great.
@adityanarayangantayat7133
@adityanarayangantayat7133 2 года назад
I've a different sort of doubt. Will the "src" provided always be the first element of the graph? Or there's no such rule and we can be provided with any element from the middle as "src"?
@vikassharma2094
@vikassharma2094 2 года назад
no there is no such rule
@adityanarayangantayat7133
@adityanarayangantayat7133 2 года назад
@@vikassharma2094 alright But the src should be a node from which all other nodes must be reachable, right?
@arpit743
@arpit743 2 года назад
@@adityanarayangantayat7133 Nope. say if src is a 1 in this graph that striver has mentioned. then the nodes 0,4 will be left having infinite distance as they can't be reached. and we would just pop these nodes of the topologically ordered stack till we reach the src node which is having 0 distance. and then from the nodes after this src node we would update the distance array. Try Dry running once with 1 you'll get it better. Also Try with BFS to see why this is so much better.
@ritikagarwal2622
@ritikagarwal2622 3 года назад
simply do topological sort for source node only then there would be those node in stack which are accessible by source and hence no need to check inf condition. Am i right or missing some case??
@naiemofficial_
@naiemofficial_ Год назад
I'm inquisitive to know about the weight of an edge in the Graph. Suppose, If I add just 3 nodes where W=Weight 0 => [(N=1, W=5), (N=2, W=3)] 1 => [(N=2, W=2)] Why in the Graph doesn't use W=1 or W=10 or any other value? How were the values calculated or defined here? Why not there's logic to set the values of weight through the program not manually?
@rajaptdr
@rajaptdr 2 года назад
So as we cant use the topo sort on the undirected graph, Can we assume that in worst case TC for find distance in Undirected is greater than directed(TC is reduced using topo sort).
@urjitdesai1998
@urjitdesai1998 2 года назад
So we can use either this method or Dijkstra's algorithm for finding the shortest path and get the same answer ?
@abhishekhorton79
@abhishekhorton79 3 года назад
what if the first node is not a source node in our stack as there can be multiple topological order so should we continue without doing any operation? eg - topological order gives you -> 4 - 0 - 5 - 1 - 2 - 3 .. and the source node is 0 in this case 4 itself has INT_MAX in it's dist array should we continue this step without doing any operation? Once again excellent explanation you're making one of the advance data structure easy to understand thanks a lot ;)
@manishagarwal5238
@manishagarwal5238 3 года назад
Yes. Since it's the first element of topo sort, it has in-degree 0 which means it is not reachable from 0 (if you are considering 0 as src node). So it should print "INF" for node 4.
@abhishekhorton79
@abhishekhorton79 3 года назад
@@manishagarwal5238 yea that's exactly I was thinking..
@deepakkashyap6538
@deepakkashyap6538 3 года назад
Correct me if I am wrong can we make the dist[st.top()]=0 instead of passing the src node and making dist[src]=0 because we can't say that the src that we are passing is having indegree as 0 and it is also not guarenteed that the src node that we are passing would be on the top of the stack after the topo sort
@harshapriya1463
@harshapriya1463 3 года назад
Why is (dist[node] != INF) check is made?
@letscode-it881
@letscode-it881 3 года назад
Bhai you have attached the wrong code links. Like i guess, links are missplaced. Do check. Some people may have some issues. Last video contained code link of this one. This contain code link of next one. Btw, thanks for contributing so much to Community ❤️
@takeUforward
@takeUforward 3 года назад
Okay will check
@ronithsinha5702
@ronithsinha5702 2 года назад
Can someone explain why do we have to find the topological sort first? Will the program give incorrect result if we don't do topological sorting?
@takeUforward
@takeUforward 2 года назад
Pinned comment.
@jaideepsingh7955
@jaideepsingh7955 2 года назад
Sir if we are going according to the topological sort, then why do we need to check if distance of a node is not infinity. Because we'll only be going to the nodes that are adjacent to the current node{the accessed node's distance will not be infinity as it will be already updated by then}, so no way of reaching a node that is inaccessible(of distance infinity) from the current node. Please explain sir. Or in what kind of case will it happen ?
@RitikPanchal-hd2ku
@RitikPanchal-hd2ku 2 года назад
Can we use priority queue instead of Topological Sort ,if not please give reason
@dhavalagrawal6388
@dhavalagrawal6388 2 года назад
what will happen if we dont check (dist[node] != Integer.MAX_VALUE) at 24:05 ?
@bhavyakapoor1109
@bhavyakapoor1109 2 года назад
Integer Overflow!
@reee896
@reee896 2 года назад
So if I wanted the shortest path between any 2 node I can just subtract their value from dis array
@suvojitray1431
@suvojitray1431 3 года назад
why is the condition if(dis[node]!=inf is used?I see that it is always true what is the corner case when it becomes false?
@takeUforward
@takeUforward 3 года назад
Because if you have not reached from soirce, how will you move ahead.
@suvojitray1431
@suvojitray1431 3 года назад
@@takeUforward Thanks dada
@ashokk2002
@ashokk2002 3 года назад
Sir, why can't we say it is better algo than dijkstras... As it is O( N+E) but in case of dijkstras it was O( N log N) , but on internet it is mentioned dijkstras is best algo for shortest path
@takeUforward
@takeUforward 3 года назад
Because this is specifically for DAG.. In djisktra, you might some other path, and it is also applicable for undirected graphs..
@gowthamreddyuppunuri4549
@gowthamreddyuppunuri4549 2 года назад
@@takeUforward Hi striver, I need some justification on my thoughts regarding shortest paths 1) Dijkstra works perfectly well for weighted undirected graphs(Cyclic and Acyclic) with no negative cycles(may contain some negative edges but not negative cycles). 2) Dijkstra works perfectly well for weighted directed (Cyclic and Acyclic) graphs with no negative weights(only positive weights) 3) The Above discussed TopoOrder Relaxing technique works for Directed Acyclic Graph with negative Edges. I need your view on above points. Hope You will answer!!!
@juhaar4508
@juhaar4508 2 года назад
Cant we do it using queue like we did for unique weight
@anantchandak5772
@anantchandak5772 3 года назад
Why are we using topo sort can any one explain?
@pulakammalathy6968
@pulakammalathy6968 2 года назад
only doubt is topological sort can be developed for only dag, if given graph is cyclic, how do we do it ?
@nilanshuyadav8608
@nilanshuyadav8608 2 года назад
please provide some question links based on the topic to just taught.
@RudraSingh-pb5ls
@RudraSingh-pb5ls 3 года назад
How about directly applying BFS here as well, the same way we did in the previous video ??
@channelname4394
@channelname4394 2 года назад
Best explanation. understood , hope this channel reaches more people
@jayeshbhanushali1745
@jayeshbhanushali1745 3 года назад
You have put the link of "Graph is Cyclic or not" in c++ Please put the link of "Shortest Path in Directed Acyclic Graph (DAG) " in c++
@akshaysingh548
@akshaysingh548 2 года назад
why the code link in the description is for the cycle detection code?
@HarshKumar-tf8mh
@HarshKumar-tf8mh 2 года назад
I just one doubt why do we need to do the topological sorting?
@snehabaser3155
@snehabaser3155 3 года назад
can't we use same approach that we are using to find shortest path in unndirected graph?
@jayantmittal6665
@jayantmittal6665 3 года назад
what if top of stack is not the source?? then how to proceed
@jagannathank6531
@jagannathank6531 3 года назад
Top of stack is always the source. The source node will be pushed into the stack only at the end.
@chiragarora870
@chiragarora870 3 года назад
Shouldn't we pop all the elements from the stack until we get our source node, and then start comparing distances???
@tusharnain6652
@tusharnain6652 2 года назад
links in the description is not of this video.
@roushanraj8530
@roushanraj8530 3 года назад
Bhaiya does it will work for negative weighted DAG also ??
@amitmohapatra292
@amitmohapatra292 2 года назад
in the example graph striver took 1 node that has indegree 0 that is the node 0 which is also an src , but what if we have 2 's indegree node for e.g. 0 & 5 and our topologiacal order came such a way that in the stack's top we have zero and our question have given that the src should be 5 Then what should i do can anyone tell me
@techzone0131
@techzone0131 2 года назад
why we are using toppological sort. can we use BFS Traversal
@takeUforward
@takeUforward 2 года назад
Takes a bit more time.. Topo sort is used so that we start from the node where there is node visiting it. Hence kond kf start point
@swapnilsingh710
@swapnilsingh710 3 года назад
why we are using topological sort here..i didn't get the intuition behind sorting first ?? what's wrong in iterating from 0-->N ? Can anybody Explain ?
@utsavraj5572
@utsavraj5572 3 года назад
Sir for directed graph we can't take source node as user input ???
@manishsahu6873
@manishsahu6873 2 года назад
Bhaiya the c++ code link is for cycle check in undirected graph using BFS
@tusharmahawar3436
@tusharmahawar3436 3 года назад
This distance array we got contains min distance from node 0 to any other node , what if they has asked min distance from node 4 ? How will we get this from this array ?
@AbhishekKumar-td5zu
@AbhishekKumar-td5zu 3 года назад
as we are setting dist[src] = 0 , it will start from there, the condition dis[node] != infinity will not let any other node than src to enter that condition first. Because of topological sort notes coming before src will be discarded.
@namansharma5128
@namansharma5128 2 года назад
can we use dijstra algo here ????????????
@pranavbalakrishnan2047
@pranavbalakrishnan2047 3 года назад
Can't this be done in a similar way to the previous one, except here we add the weight instead of 1?
@zacian4941
@zacian4941 3 года назад
yeah but time complexity will also increase in that case, since we are updating nodes distances and pushing nodes in Queue again and again
@rohandeshmukh3989
@rohandeshmukh3989 3 года назад
@@zacian4941 actually in previous algo if you observe you were getting the shortest path at the first visit of that node only after that there were happening comparisons but the value wouldn't had been changed means you are pushing the value of node in queue only when the dist of it (node) is INF so i think it will work in the same tc of bfs of O(V+E) ,correct me if i am wrong
@acking2967
@acking2967 3 года назад
Awesome explanation bhaiya..ur videos cleared all my doubts..thk u so much
@_-6912
@_-6912 3 года назад
Hi Raj, I guess the Java code link is pointing towards the Cycle detection not for shortest path code.
@lokeshnegi5051
@lokeshnegi5051 2 года назад
can anyone explain why we haven't used topo sort for DAG unweighted.
@amitupadhyay2445
@amitupadhyay2445 2 года назад
the code in the discription is not of shortest path it is of cycle detection in case of java code please update it.
@kage-musha1702
@kage-musha1702 3 года назад
since this is directed we can also use kahn's algorithm right ? :P
@varunmanchanda3972
@varunmanchanda3972 2 года назад
Can we use this algorithm if weights are negative also?
@tusharabbott
@tusharabbott 2 года назад
yes
@ashirbad29
@ashirbad29 3 года назад
instead of topological sort, can we just do a BFS from source and find the distances, if not then why
@takeUforward
@takeUforward 3 года назад
Because there are edge weights, had the edge weights been 1, then we can think of that, but here that is not the case.
@aayushisingh3280
@aayushisingh3280 3 года назад
I tried it and it seems to work. I added the edge weights instead of adding 1. Here's my python code: class Graph: def __init__(self, vertices): self.graph = [ [] for i in range(vertices)] self.vertices = vertices def addEdge(self, src, dest, wt): self.graph[src].append((dest, wt)) def dispGraph(self): for i in range(len(self.graph)): print(i, end=" -> ") for edge in self.graph[i]: print(edge, end = ", ") print() def findShortestPath(self, src, dest): distances = [float('inf')] * self.vertices distances[src] = 0 q = [] q.append(src) while q: node = q.pop(0) for nbr in self.graph[node]: if distances[node] + nbr[1]
@takeUforward
@takeUforward 3 года назад
@@aayushisingh3280 u need to try a lot of examples, can you try submitting.
@adityapundir5549
@adityapundir5549 3 года назад
Yes, I also solved the problem without using topological sort and it did work, am not getting the correct intuition to use topological sort here, can someone explain me?
@takeUforward
@takeUforward 3 года назад
@@adityapundir5549 When you use a bfs, you are not sure which is the starting point, hence it might happen you have to iterate in the queue many times, when you use topo sort, you are sure this is the first node which has no incoming nodes. Hence you start from the starting point, hence taking lesser amount of time. While using BFS, you are not sure if your source is the starting point or not, if it is not, then you will be taking extra turns.
@gurharpartapdhaliwal3087
@gurharpartapdhaliwal3087 3 года назад
So why topo sort work This is what i think The nodes which are above src in stack are non reachable so the check of dis[node]!=inf works. after that all nodes are visited in order of their dependencies like a node 3 will be reahced by all the nodes pointing to it and we will just take the minimum out of them.
@learnwithme7750
@learnwithme7750 3 года назад
Loved your explanation bro
@sahilmistry2898
@sahilmistry2898 3 года назад
Sir why we are taking toposort.?
@kumarharsh90
@kumarharsh90 3 года назад
since we did topo sort why are we even checking dis[node]!=if;
@utkarshsharma6650
@utkarshsharma6650 2 года назад
is there any leetcode/gfg practice link?
@snehabaser3155
@snehabaser3155 3 года назад
What happens if source node given having more than or equal to one incoming edge ? Then which node enters in dist[node] loop first?
@AbhishekKumar-td5zu
@AbhishekKumar-td5zu 3 года назад
as we are setting dist[src] = 0 , it will start from there, the condition dis[node] != infinity will not let any other node than src to enter that condition first. Because of topological sort notes coming before src will be discarded.
@niksgupta36
@niksgupta36 2 года назад
Could we use Dijkstra's algo on DAG to find shortest distance?
@karanrocks4447
@karanrocks4447 2 года назад
Yes U can use. Dijkstra works in all cases except negative edge weight
@narendrarokkam5367
@narendrarokkam5367 2 года назад
Could anyone can help me if we don't use the if condition (dist[node] != Integer.MAX_VALUE) we are getting same output
@narendrarokkam5367
@narendrarokkam5367 2 года назад
But y we need to use
Далее
Cycle Detection in Directed Graph using DFS
21:26
Просмотров 165 тыс.
ХУДШИЕ ВЫБОРЫ в США
13:20
Просмотров 477 тыс.
Graph Algorithms for Technical Interviews - Full Course
2:12:19
G-41. Bellman Ford Algorithm
27:43
Просмотров 223 тыс.
11  Single Source Shortest Path in DAG
18:29
Просмотров 4,8 тыс.