G-27. Shortest Path in Directed Acyclic Graph - Topological Sort

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79

[@sukhpreetsingh5200]

thnks a lot for this amazing content. understood🙂🙂

[@suhaanbhandary4009]

Thanks for such a great series 😃

[@sudhanshushekhar4222]

understood

[@sairam3351]

understood

[@khushioswal1291]

understood😄

[@visase2036]

Shortest path from any src : 1.Perform toposort and store the order in a stack 2.Once the source node is given, pop the elements in the stack until the stack's top is the source 3. Rest is the same . Eg : For src 5---> dist=[4,6,2,5,1,0,inf] 6->inf because you cannot reach 6 from 5

[@gsmdfaheem]

Thanks for this!!!

[@advaitshah3190]

Thank you

[@siddharthchauhan961]

This needs to be pinned. I could've saved 20 minutes

[@subhamoyburman3093]

Thanks for this. Got fully confused by the example.

[@umangrockstar236]

defenetely an underrated comment the examples will make u think this through btw ... thanks for this

[@RaghavSharma-nt3hr]

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)

[@ayushsharma-dz4dl]

Much much thanks for this , thinking about the same thing for last 3 days.

[@jambajuice07]

code for solution with bfs class Solution { public: vector shortestPath(int N,int M, vector& edges){ vectordist(N ,INT_MAX); // creating a adj vectoradj(N); for(int i=0;i=dist[nei])continue; dist[nei]=price+distance; q.push({nei , dist[nei]}); } } } for(int i=0;i

[@sumitkevlani5740]

But I have stored the topological sort in an array using bfs just like we are doing using dfs within a stack. That code also is not working. I have rechecked the code so many times it is right but i am unable to understand the problem with it. @stoic this code is of simple dijsktra algorithm where we are again pushing the pair when we updated the distance. We need to solve it more efficiently.

[@AniRec-e8u]

i fiirst did this question on my own and solved it using the bfs approach now i was not able to understand why to find topo sort if we can simply do the question with bfs. Thanks for the explanation bro...

[@itspurelypassionate]

Thanks I was wondering about that

[@punyashloknath1990]

Guys if the source node is not the first element of topo sort then in that case it is not possible to reach all the nodes from the source. so, question are designed in such a way so that from source node it is always possible to reach all of remaining nodes,thats why we choose source node as a first element of topo sort.

[@tejasparse9053]

For those who are wondering if it can be done with Topology Sort using BFS, YES it can be done. Instead of doing dfsTopo, just do bfsTopo. Very carefully then go through topo array and see if the topo[i] is reachable vector topoSort = bfsTopo(N, graph); vector distance(N, -1); int start = 0; distance[start] = 0; int i = 0; while(i

[@divyareddy7622]

i did'nt understand why this and next question can't be done using Dijkstra's algo? could you please explain?

[@tanishagarwal5992]

Some common things which I understood :- 1) This can be done by simple BFS but there will be many redundancies in it that's why we use topo sort to avoid such redundancies. 2) What if source node is not on the top or if whichever node is at top for that the distance has not been yet calculated? In that case that node is unreachable from source and we can skip its neighbours' exploration i.e. if(dist[node]==-1) continue; .... if we have assigned all distances by -1 initially 3) Had the edges been all of uniform weight then there would have been surity that there would be no redundancies in the BFS and thus no need of TOPO sort would have been there just like the next video where in an undirected graph all the weights are one.

[@dikshantsharma9409]

u don't know how much u have made graph easy for a naive coder like me!

[@scholarshiphelp5999]

Thank you Striver for this commendable work. ⭐ A BIT OF OPTIMIZATION I have an observation. Please correct me if I'm wrong. I think we do not need to call the topoSort for all the disconnected components. Since we are only interested in src node. topoSort(src,adj,vis,st) is enough. This saves us from having to dfs the whole graph (unreachable part from src and disconnected components). Plus this will always ensure the src node is at the top of the stack.

[@acciocoder6596]

Insightful Ma,n!!. It works...thanks.

[@srinivasbeta8202]

true we can save lot of time because anyhow we cant reach the disconnected components from our source...so just do dfs once starting from src node

[@jashanswork]

Nice observation man

[@chow3439]

Nice observation

[@jivanmainali1742]

yeah but you need to make sure it has no cycle , if we call on every node we can check for cycle by vertices number not equal topsort length

[@mmbmmbmmb]

now theres few changes in questions basically we have to change those elemnts whose distance is still infinity to -1 //{ Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends // User function Template for C++ class Solution { public: void toposort(int node,vectoradj[],int vis[],stack&st){ vis[node]=1; for(auto it:adj[node]){ int v=it.first; if(!vis[v]) { toposort(v,adj,vis,st); } } st.push(node); } vector shortestPath(int N,int M, vector& edges){ // code here vectoradj[N]; for(int i=0;i> m; vector edges; for(int i=0; ix; temp.push_back(x); } edges.push_back(temp); } Solution obj; vector res = obj.shortestPath(n, m, edges); for (auto x : res) { cout

[@Sakshi_Raj67]

thanks

[@divyareddy7622]

i did'nt understand why this and next question can't be done using Dijkstra's algo? could you please explain?

[@Aditya-kumar-129]

Hii everyone So the question and the corresponding solution for the question discussed by the striver bhaiya have been changed(It seems like the problem setter has worked on it. the one that striver bhaiya was talking about) So as per the current question, we have to return -1 when we aren't able to reach the node from the source node. So we just have to add and modify the code at the end :- for (int i = 0;i < N;i++) if (dist[i] == 1e9) dist[i] = -1; Just add these two lines before returning the answer. The whole code looks like this :- class Solution { private: void topoLogicalSort(int src, vector adj[], stack& st, vector& visited) { visited[src] = 1; for (auto it : adj[src]) { int v = it.first; if (!visited[v]) topoLogicalSort(v, adj, st, visited); } st.push(src); } public: vector < int > shortestPath(int N, int M, vector < vector < int >>& edges) { // Step 1 :- Convert the given adj list into this form vector < pair < int, int >> adj[N]; for (int i = 0; i < M; i++) { int u = edges[i][0]; int v = edges[i][1]; int wt = edges[i][2]; adj[u].push_back({ v,wt }); } // Perform the topological Sort vector < int > visited(N, 0); stack < int > st; for (int i = 0; i < N; i++) if (!visited[i]) topoLogicalSort(i, adj, st, visited); // Step 3:- Relax all the edges one by one from the stack vector < int > dist(N, 1e9); dist[0] = 0; while (!st.empty()) { int node = st.top(); st.pop(); for (auto it : adj[node]) { int v = it.first; int wt = it.second; if (dist[node] + wt < dist[v]) dist[v] = dist[node] + wt; } } for (int i = 0;i < N;i++) if (dist[i] == 1e9) dist[i] = -1; return dist; } };

[@takeUforward]

Yes I told him to update it. Kese nai karega 😉

[@harshitsharma5647]

yes when the value of dist[i] is equal to 1e9 then -1 Question update kyu nhi hogaa paata nhi hai kisne kaha striver AKA Appne bhaiya ne Again and again Thankyou bhaiya for alot of guidance us.

[@mohakhiphop]

Thanks man🤝

[@DevanshuAugusty]

what is 1e9?

[@Aditya-kumar-129]

@@DevanshuAugusty pow(10,9);

[@loveleshbhagat1114]

Why TopoSort is used for Calculating Shortest path in DAG ? Explanation : The use of topological sorting in your code for calculating the shortest path in a Directed Acyclic Graph (DAG) is a crucial step. Here’s the intuition behind it: Why Topological Sort? Linear Ordering: -->Topological sorting provides a linear ordering of vertices such that for every directed edge ( u-->v ), vertex ( u ) comes before ( v ) in the ordering. --> This property is essential for processing nodes in a way that ensures all dependencies (incoming edges) of a node are processed before the node itself. Efficient Distance Calculation: --> In a DAG, once we have the topological order, we can process each vertex and update the shortest path distances to its adjacent vertices. --> By processing nodes in topological order, we ensure that when we process a node, all nodes that can reach it have already been processed. This guarantees that we have the shortest distance to the current node before we try to update the distances to its neighbors. Steps Involved in Code: Topological Sort: We perform a Depth-First Search (DFS) to generate a topological sort of the graph. This ensures that each node is processed only after all nodes that can reach it have been processed. The nodes are pushed onto a stack in the order of their finishing times in the DFS, which gives the topological order when popped from the stack. Shortest Path Calculation: Initialize the distance to the source node (node 0) as 0 and all other nodes as a large value (infinity). Process each node in topological order. For each node, update the distances to its adjacent nodes if a shorter path is found through the current node. This ensures that by the time we process a node, we have already found the shortest path to it, and we can use this information to update the shortest paths to its neighbors. Example: Consider a simple DAG with edges and weights: 0 -> 1 (weight 2) 0 -> 2 (weight 4) 1 -> 2 (weight 1) 1 -> 3 (weight 7) 2 -> 3 (weight 3) Topological order might be: 0, 1, 2, 3. Start with distances: [0, ∞, ∞, ∞]. Process node 0: Update distances to 1 and 2: [0, 2, 4, ∞]. Process node 1: Update distance to 2 and 3: [0, 2, 3, 9]. Process node 2: Update distance to 3: [0, 2, 3, 6]. By processing nodes in topological order, we ensure that when we process a node, we have already found the shortest path to it, allowing us to correctly update the shortest paths to its neighbors. Conclusion: Topological sorting is used to ensure that we process each node only after all nodes that can reach it have been processed. This guarantees that we have the shortest path to each node before we use it to update the shortest paths to its neighbors, making the algorithm efficient and correct for finding the shortest paths in a DAG.

[@GauravKumar-t2z7v]

Thanks a lot sir❤! U have made it really easy for us to understand👌👌. FYI this question is modified now, so we need to add this snippet before while loop for the code to work👇: for (int i = 0; i < N; i++) { if(stack.peek() != source){ int node = stack.pop(); dist[node] = -1; } else break; } Here is the whole code in java for reference👇: class Pair{ int first; int second; Pair(int first, int second){ this.first = first; this.second = second; } } //User function Template for Java class Solution { public static void dfs(int node, int[] vis, Stack stack, ArrayList adj){ vis[node] = 1; for (Pair i : adj.get(node)) { if(vis[i.first] == 0){ dfs(i.first,vis,stack,adj); } } stack.push(node); } public int[] shortestPath(int N,int M, int[][] edges) { ArrayList adj= new ArrayList(); for (int i = 0; i < N; i++) { adj.add(new ArrayList()); } for (int i = 0; i < M; i++) { int u = edges[i][0]; int v = edges[i][1]; int weight = edges[i][2]; adj.get(u).add(new Pair(v,weight)); } int source = 0; int dist[] = new int[N]; for (int i = 0; i < N; i++) { if (i == source) dist[source] = 0; else dist[i] = Integer.MAX_VALUE; } int vis[] = new int[N]; Stack stack = new Stack(); for(int i=0; i

[@shreyanshagrawal3115]

thanks so much, got stuck there

[@udayvivek717]

thanks bro

[@nishthapaul3264]

But, what is the stack has (some nodes which cannot be visited by 0 - which you removed by additional logic), source i.e. 0, again (some nodes which cannot be visited by 0 - which you removed by additional logic) , nodes which can be visited by 0. how will you remove or ignore the second group of nodes which cannot be visited by 0 ?

[@Kanishk-rb7zx]

The question again has been modified. If there is something else (not 0) at the top of the stack, we must not process that and simply keep popping it until we encounter 0 at the top. vector dist(N,INT_MAX); dist[0]=0; bool flag = true; while(!st.empty()) { int nnode = st.top(); if(nnode != 0 && flag) { st.pop(); continue; } if(nnode==0) { flag = false; } int d = dist[nnode]; st.pop(); for(auto nbrs : adj[nnode]) { int node = nbrs.first; int dd = nbrs.second; dist[node] = min(dist[node],dd + d); } }

[@vaibhavsoni2437]

Or just check at the end (before returning), if any value of distance == 1e9 and replace it with -1.

[@kryptexFPS]

Another method : Instead of following code for visiting all nodes with dfs : for (int i = 0; i < N; i++) { if (!vis[i]) { topoSort(i, adj, vis, st); } } Do this : You can just give one starting dfs call from source node(0) and it will only visit those nodes which are reachable from 0. int src = 0; topoSort(src, adj, vis, st);

[@DevanshuAugusty]

@@vaibhavsoni2437 what is 1e9

[@DevanshuAugusty]

thanx man

[@lakshsinghania]

@@DevanshuAugusty 1x10^9

[@the_haryannvi_coder]

Other method than topoSort:- Using same logic used in undirected graph with unit weights:- vector shortestPathInDAG(int n, int m, vector &edges){ // creating adj list vector adj(n); for(int i=0; i ans[tnode] + it.second){ ans[it.first] = ans[tnode] + it.second; q.push(it.first); } } } for(int i=0; i

[@krishnashah6654]

This would give WA in cases when the first element in the TOPO stack is not the source node. Then it's initial dis would be INF and we'd proceed to fill other dis using it. Pop all the stack elements, until you reach the source node. Source node should be the first element in the stack, had it been this way. Working 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 node, vector& vis , stack& st, vector adjList[]){ vis[node] = true; for(auto child : adjList[node]){ if(!vis[child.first]){ dfs(child.first, vis, st, adjList); } } st.push(node); return; } vector shortestPath(int n,int m, vector& edges){ vector dis(n , INT_MAX); vector vis(n , false); vector adjList[n]; for(int i = 0 ; i

[@parallax8916]

Finally some said it ... I was thinking the same all along watching the vdo. And when I tried to submit the code,same issue occured. I was really trying hard thinking about the solution and finally u helped it !!! Thanks man

[@gmh14]

This should be the top comment, surprised how no one is noticing this issue

[@itsmepratham2712]

Exactly Striver Should pin this

[@Stickman-rz9nu]

thanks, finally understood it

[@AppaniMadhavi]

I have been thinking for 3 hours, that how striver got that, but finally after seeing to your comments relaxed, thanks bhai doubt resolved..

[@AnshulVerma-cd1od]

I have seen a lot of Graph playlists but this is on some next level. After watching this my all concepts are cleared.

[@findingshrek]

I believe the question has been updated. We need to return -1 for un reachable index. public class ShortestPathInDAG { public static class Pair { int node; int weight; public Pair(int node, int weight) { this.node = node; this.weight = weight; } } //Topo sort using dfs private void topoSort(int start, int[] visited, List adj, Stack stack) { visited[start] = 1; List adjacentNodes = adj.get(start); for (Pair p : adjacentNodes) { if (visited[p.node] != 1) topoSort(p.node, visited, adj, stack); } stack.push(start); } public int[] shortestPath(int N, int M, int[][] edges) { List adj = new ArrayList(); for (int i = 0; i < N; i++) { adj.add(new ArrayList()); } for (int i = 0; i < M; i++) { int[] edge = edges[i]; adj.get(edge[0]).add(new Pair(edge[1], edge[2])); } int[] visited = new int[N]; Stack stack = new Stack(); //Topo sor for every component for (int i = 0; i < N; i++) { if (visited[i] != 1) topoSort(i, visited, adj, stack); } //We need to find the distance. int[] distance = new int[N]; for (int i = 0; i < N; i++) { distance[i] = -1; // We need to return -1 for unreachable edges. } int source = 0; distance[source] = 0; //Since question has stated , start will always be 0; //Making sure 0 is on top of stack. Anything before 0 does not make sense because there are no egdes from zero to elements before it. while (stack.peek() != source) { stack.pop(); } while (!stack.isEmpty()) { int node = stack.pop(); int distanceFromSource = distance[node]; // this is the shortest from source to this node distance. List adjacentNodes = adj.get(node); for (Pair p : adjacentNodes) { int newDistance = distanceFromSource + p.weight; if (distance[p.node] != -1) { if (distance[p.node] > newDistance) { distance[p.node] = newDistance; } } else { distance[p.node] = newDistance; } } } return distance; } }

[@rushidesai2836]

Helpful. Thanks.

[@nidhimanek4565]

when a node comes up in topo sort, all the possible paths to reach that node are considered (as in-degree has become 0), that's why when we pop it out from the stack, whatever distance is stored in distance array is the final distance for that node.

[@chandlerbing8164]

I think instead of TOPO sort we can use simple BFS from the source node and since there is no cycle it will work perfectly fine. if source can not reach other nodes it is fine as we do not need to process them at all. I implemented it on GFG and Coding Ninjas's portal and it works perfectly fine.

[@VenugopalaSwamy-fb3se]

1014/1121 passed after that i got TLE

[@dank7044]

it will have more TC than the toposort logic,since you'd need to revisit a node's adjacent/child nodes if you encounter a shorter path for them in the future again

[@surendharv795]

@@dank7044 You are right.

[@ayushyadav8665]

The question has been modified just add this snippet in the end for(int i=0; i

[@deepakagrawal7687]

toposort ensures that when moving from point A - B, A has the smallest path value from source, so when moving from B-C path will be smallest till C from source. with bfs this is not guranted and so re-reduction of further path is needed and so if new path comes to A with small value then previous value then re computation of path from A-B-C is needed.

[@stith_pragya]

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

[@stillness-in-motion]

Understood. You are an awesome mentor/tutor. What an explaining skills you have . Great job Striver.🤗

[@sripriyapotnuru5839]

Thank you striver for clear explanation and also adding such stack over flow posts , it improves the learning experience.

[@rickk3300]

where is the link to the stackoverflow post?

[@manohar0742]

@@rickk3300 I too cannot see it.

[@YashwanthsaiCh]

Neeku acakada kanipinchindi ey aa link

[@iamnottech8918]

normal code for this question without toposort // tc ~=o(V+2E) // sc ~=o(V) class Solution { public: vector shortestPath(int N,int M, vector& edges){ // creating an adjacency list // same as undirected // here point to note that is wt is given so we // cannot store the wt in the adj as 2nd index as there can // be multiple connections to it as one node may have many connections // so the only way that is left is to store pair so we will be // storing vector of pair's due to which the code looks somewhta // complex but if we have understanding of this ds we will use concept // is same // eg for like // 0 1 2 // 0 4 1 // now 0 index in adj. will have like [{1,2},{4,1}] // where first is edge and 2nd is weight // concept is cleared . vectoradj(N); // vectordistance(N,1e9); for(int i=0;i

[@jayjoshi693]

The question has now been modified by GFG, now you have to keep dist = -1 if its not reachable from the source node. hence, add the following code snippet in your code: for(int i=0; i

[@39_jatinjain4]

why we can't take INT_MAX

[@athena_gaming4852]

because then ans[node] will be INT_MAX by default and it you try to add weight into it then it will start overflowing and will become some number near to INT_MIN and thus you will get wrong answer. I did the same mistake that's why I figured it out. Like the comment if it helped you :) . @@39_jatinjain4

[@priyanshkumar17]

@@39_jatinjain4 INT_MAX can overflow during calculation of distances

[@TarunKumarSaraswat]

your code is super simple to understand

[@divyamkumar9558]

Can you kindly add timestamps for imp stuffs like intuition, code ,Time complexity and stuffs in the description..

[@mayankrohilla4105]

If you are solving this problem on gfg now, more testcases were added so we will have to tweak the given code the corrected code is : #include using namespace std; class Solution { public: vector shortestPath(int N, int M, vector& edges) { // Graph representation vector adj[N]; // Build the adjacency list for (int i = 0; i < M; i++) { adj[edges[i][0]].push_back({edges[i][1], edges[i][2]}); } // Topological Sort vector indegree(N, 0); for (int i = 0; i < N; i++) { for (auto &it : adj[i]) { indegree[it.first]++; } } queue q; for (int i = 0; i < N; i++) { if (indegree[i] == 0) { q.push(i); } } vector topo; while (!q.empty()) { int node = q.front(); q.pop(); topo.push_back(node); for (auto &it : adj[node]) { indegree[it.first]--; if (indegree[it.first] == 0) { q.push(it.first); } } } // Distance initialization vector dist(N, INT_MAX); dist[0] = 0; // Assuming 0 is the source vertex // Relax edges in topological order for (int i = 0; i < topo.size(); i++) { int node = topo[i]; if (dist[node] != INT_MAX) { for (auto &it : adj[node]) { if (dist[node] + it.second < dist[it.first]) { dist[it.first] = dist[node] + it.second; } } } } // Replace INT_MAX with -1 to indicate unreachable vertices for (int i = 0; i < N; i++) { if (dist[i] == INT_MAX) { dist[i] = -1; } } return dist; } };

[@iamnoob7593]

great intuition yet simple

[@amanmaurya7608]

My approach without toposort void dfs(int node , vector&minpath, vectoradj[]){ for(auto it : adj[node]){ minpath[it.first]=min(minpath[node]+it.second,minpath[it.first]); dfs(it.first,minpath,adj); } } vector shortestPath(int N,int M, vector& edges){ // code here vectorminpath(N,1e9); minpath[0]=0; vector adj[N]; for(int i=0;i=1e9)it=-1; } return minpath; } 🙂

[@anantduhan5748]

thank you @striver for helping us in logic building and making the tougher problems like a piece of cake

[@shivamtiwari8106]

best graph playlist ever

[@antor.morsalin]

in this case to perform the toposort, you can call dfs only for the starting node.

[@utkarshverma3314]

the question has been updated and we need to return -1 instead of 1e9 for all the unreachable nodes so before returning dist replace all the remaining 1e9 in the dist vector with -1

[@raven_claw887]

He has god level explanation skills.

[@dhirenparekh2646]

This is DFS approach. What will be the T.C for this? void dfs(int node,vector &adj,vector&shPath,int step){ //if the node is visited and the distance is already lesser than step then no meaning of going ahead. if(shPath[node]!=INT_MAX and shPath[node]

[@sayakghosh5104]

Such a simple explanation, Understood!

[@evilpollination1916]

Kya samjhaya hai 👏👏👏 Understood.

[@vishalsinghrajpurohit6037]

It could have also been done with a simple dfs(which will offcourse will traverse like topo sort as it's an acyclic graph). Then as we reach a node just put the min(sumof node, new sum of node). Then return the ans array. void dfs(vector&vec,vector&ans,int node,int sum){ ans[node] = min(ans[node],sum); for(auto &it: vec[node]){ dfs(vec,ans,it.first,sum+it.second); } } vector shortestPath(int n,int m, vector& edges){ vector vec(n); for(int i=0;i

[@rachanikhilrnr]

Great man that's what I have been looking for

[@lakshmanvengadesan9096]

I don't understand one thing. Here we have assumed that the source node is the first element in the topSort. What if it's not? In that case , for the nodes before the source node in topSort , the distance should be infinity right?

[@TarunSharma007]

yes ,i have also same doubt like what if source node is different and top element of stack is different ..then to reach neighbour i will be infinite + distance ...which is wrong 🥲🥲🥲

[@imajt5]

Yes Even I have the same doubt....in the code he defined distance[0] = 0; but zero node is not the source node, by the explaination and from the stack, we are taking 6 as source node

[@deviprasad_bal]

if the top of stack is not the source node, then you just need to pop out the stack until the top element is the source and then solve like as it is(since the elements popped out has infinite distance hence it doesn't matter if it gets popped out)

[@lankesubramanyam3284]

Yeah! Dist for nodes before source in toposort should be inf only

[@RajeevCanDev]

Just pop them out upto the desired src node and then apply the same... Because in topo sort every element before the desired src in the stack will never be reached through src node bcuz the graph is uni directed so we just reached only elements which are below the desired src in the stack

[@pureshwargonekar9787]

using BFS: Intuition: Relax the dist[ ] when indegree of adjacent node going to decrease in topo sort algo class Solution { public: vector shortestPath(int V, int M, vector& edges) { int inf = 1e9; // A large value to represent infinity int indegree[V] = {0}; vector ans(V, inf); // Initialize all elements with infinity ans[0] = 0; vector adj[V]; for (auto it : edges) { adj[it[0]].push_back({it[1], it[2]}); } for (int i = 0; i < V; i++) { for (auto it : adj[i]) { indegree[it.first]++; } } queue q; for (int i = 0; i < V; i++) { if (indegree[i] == 0) { q.push(i); } } while (!q.empty()) { int node = q.front(); q.pop(); for (auto it : adj[node]) { int newCost = ans[node] + it.second; if (ans[it.first] == inf || ans[it.first] > newCost) { ans[it.first] = newCost; } indegree[it.first]--; if (indegree[it.first] == 0) q.push(it.first); } } // Convert unreachable nodes (with infinite distance) to -1 for (int i = 0; i = inf) { ans[i] = -1; } } return ans; } };

[@492_alokjha9]

Isn't this algo same as doing a BFS traversal from the source? If this is DAG the source must not have any edge before it if there is any it would be infinity. I feel rest cases is same as doing a bfs from the source the only diff is you don't need to store the adjacent nodes here as the next element to it are already known with topo sort. Topo sort gives us the order of the element what if the source given to us is not the first element rather somewhere between? We will be only doing those some extra infinity+wt for all those element before the source. While using BFS when you initialized the distance vector you only had to traverse from there adding the weight for min weight? I was unable to understand how topo sort helped us finding a efficient path. Yes it would be beneficial if we use the dfs approach as there we only will be increasing our stack memory with recursion calls for same element. But when we use BFS will it really give us a more effective solution? Kindly help me with this doubt.

[@apmotivationakashparmar722]

Thank you So much Striver !

[@jackryan7626]

if the source node is something else, just obtain the distance array as it is, but then subtract the distance of the source at all the indices (basically make the src dis=0), then you will get some indices where where indices are less than 0 those are the nodes that cant be reached.

[@jackryan7626]

some nodes where value of dis < 0 , are the nodes that cannot be reached

[@dank7044]

no need to do this,code works normally too,just initiate your vec with a large val

[@harshexploring4922]

i wish i could explain like you in the interviews

[@AppaniMadhavi]

I think without topo sort we can do, by taking src node into queue first then whenever the distance changed for their adjacent nodes they will be pushed into queue!!!

[@XyzAbc-ob2sz]

What if src is not top element of stack?? Ans: for an example let's take 4 as our src node. While popping out in 2nd step , we will get dist INFINITE. No worries. Bcz this is toposort. That simple means we can reach from 6 to 4. But not 4 to 6. As 4 is our src, we can't reach to 6 ,so dist will be INFINITE.

[@breakthecode8323]

Bhaiyaa, thank you so much for graph series, per bhaiya please can you also make series on segement trees, tried learning from so many places, but nowhere satisfactory content is found, bana do na bhaiya ek series please

[@gsmdfaheem]

Already banai hai.... Just youtube pr search striver segment trees... Dusre koi channel pe hai jahan pehle bhaiya padhate the.... Take you forward pe bhi hai kuch 2 years ago daala tha

[@breakthecode8323]

@@gsmdfaheem will check out, thanks for pointing out.

[@gsmdfaheem]

@@breakthecode8323 no problem

[@ThatNibbah]

Thank you sir for providing this awesome videos, but I think for every solution intuition should come first ,doing dry run of code then talking about the intuition wasn't helpful for me , plus I think this video should be after G-28 since it's a weighted graph. Thanks

[@rajsng1]

really loved explaination

[@vyomgoyal3125]

What's the need to do the TOPO sort first? I think we can do it simply without topo sort as well???

[@rishabhranjan5162]

Do the topo short, Take node out and keep updating the distances.

[@pradiptabanerjee3161]

Hello sir, I have a query that, I try to solve this problem with simple BFS, like you taught in Shortest Path Finding in Undirected Graph and that algorithm is running fine then why we have to take topoSort at first?? Is it for those test cases where the source nodes can be any thing ?? Because then we have to find out that node which doesn't has any parent node. I this the normal BFS works for my case because the source node is always 0 at GFG's problem. I'm little bit confuse in this. Please tell me is it right what I'm thinking or there are some other reason for doing the topological sort at first.

[@PanchalHappy]

Nicely explained

[@mount2020]

why do we use 1e9 instead of INT_MAX ?? This concept can be understood considering any node from the component that is not reachable to the source node. The component is unreachable because it is nowhere connected with the component which has source node as one of its nodes. Suppose I have initialized distances[i] = INT_MAX and take a node from the stack and the node belongs to the unreachable component. Now if I do distances[u] + wt, the memory overflows...distances[u] is already INT_MAX and if u go to add something more it will overflow. Thus to escape from this we minimise the value from INT_MAX to 1e9. Now u can add wt to it and there will be no overflow. I have used INT_MAX instead of 1e9...didn't store those nodes which are unconnected or unreachable to the source node private: void dfs(int node, vector adj[], stack &st, vector &visited){ visited[node] = 1; for(auto adjPair : adj[node]){ int adjNode = adjPair.first; if(!visited[adjNode]) dfs(adjNode, adj, st, visited); } st.push(node); } public: vector shortestPath(int N,int M, vector& edges){ //create a adjacency list from the given input //where 1 column contains u and 2nd column contains v and 3rd columns //contains wt vector adj[N]; for(int i=0; i

[@shivangsaxena8795]

thanks for you solution!

[@yashwanthreddy1567]

if topo sort's first element is different from src then ?

[@raghavmanish24]

things we have to perform when source is any other no .......before traversing the stack for relaxing edges we have to pop the stack untill we got source then only we have to traverse stack for relaxing edges .

[@shakthisri8409]

Shouldn't that adj declaration be vector< vector< pair> > adj (N); ??

[@dank7044]

this will work too,but striver actuallt declared an array,where each el is vectro

[@lightyagami7488]

So this algo will only work when my src node has the highest outdegree......Can someone please tell me if I am right or not?

[@armaanhadiq3741]

really impressive approach

[@ganeshvernekar2797]

what if stack top is not equal to source?

[@ganeshvernekar2797]

Now got the answer, That is pop the elements of the stack until we obtain the source node , Because the element above the source node in the stack cannot be travelled with the element below to it

[@shivasai7707]

@@ganeshvernekar2797 thanks bruh 🙌

[@imajt5]

@@ganeshvernekar2797 Thanks you Ganesh bhai you clear my doubt as well

[@MrX-il2jt]

​@@ganeshvernekar2797👏👏👏

[@cinime]

Understood! What an amazing explanation as always, thank you very much!!

[@mddinislam08]

I used this into CSES 'Shortest Path 1', but got some WA in some Test Cases... without Dijkstra is it not possible by using this ?

[@potassium_cyanide_boy8515]

bro what if source node is not a top most node in stack ? I think it is only working if source node is top node of stack of topo sort

[@StoriesFromWeb13]

better approach in terms of BFS(I did it myself)- // User function Template for C++ class Solution { public: vector shortestPath(int V, int E, vector& edges) { vector Indegree(V, 0); vector adjList(V); vector Sequence(V, INT_MAX); Sequence[0] = 0; queue q; for (auto &entry : edges) { adjList[entry[0]].push_back({entry[1], entry[2]}); Indegree[entry[1]]++; } for (int i = 0; i < V; i++) { if (Indegree[i] == 0) q.push(i); } while (!q.empty()) { int t = q.front(); q.pop(); for (auto &node : adjList[t]) { int u = node.first, weight = node.second; if (Sequence[t] != INT_MAX && Sequence[u] > Sequence[t] + weight) { Sequence[u] = Sequence[t] + weight; } if (--Indegree[u] == 0) { q.push(u); } } } for (int i = 0; i < V; i++) { if (Sequence[i] == INT_MAX) Sequence[i] = -1; } return Sequence; } };

[@sripriyapotnuru5839]

Thank you, Striver 🙂

[@knowledgedoctor3849]

We may give here one condition like if dist[node]! = 1e9 then we further calculate the distance cz dist[node]+wt for 6 It's Infinity + wt so It's calculate this one again & again untill It's found

[@_hulk748]

Understood sir thankyou so much🙇‍♂🙏🙏❤

[@morningstar1913]

where's the stack over flow link ?

[@kaichang8186]

understood, thanks for the great video

[@adityakhare2492]

I uses Dijsktra algorithm for DAG and it works fine

[@chakradharthota1100]

But time complexity is high

[@UECAshutoshKumar]

Thank you sir

[@deepakgoyal1643]

using dfs and bfs both sol is given here void toposort(int vis[], int node, stack&st, vectoradj[]){ vis[node] = 1; for(auto it: adj[node]){ if(!vis[it.first]){ toposort(vis, it.first, st, adj); } } st.push(node); } public: vector shortestPath(int N,int M, vector& edges){ vectoradj[N]; for(auto it: edges){ adj[it[0]].push_back({it[1], it[2]}); } // using dfs approach // int vis[N] = {0}; // stackst; // for(int i=0; i

[@KeerthiReddyKolan]

What is the intuition behind this solution?

[@CS090Srikanth]

I think there is no need of traversing through the all the connected components we start from source and travel through all the nodes that are connected to it directly or indirectly . In the other component the source will not be connected there is no path. So travelling through all the nodes in the same component is enough

[@itsaryanb9316]

can anyone share me the link of this question?? i cant open up the link in the description :/

[@himanshukaushik9223]

Anyone can tell vector ka pass 3 guy kaisa hai wt defined kaisa kara samaj nahi (2,1)(3,2) inside curly braces weight ko hum kaisa access kar rahe hai

[@nihalrawat1431]

Understood Striver❤

[@mihirsaini592]

Thanks man..for everything

[@preksharai2354]

There is a loophole, suppose a node n has not been reached from the source node and it's value in distance array is infinity. It has got a child as x . x was also reachable from source and has been given the distance when reached from source in distance array. Now from node n we are going to node x. To update the distance of x, we will do : dist[n]+wt = infinity+wt which is a negative value and dist[x] will be replaced. so wrong ans .

[@ishitapathak676]

class Solution { public: void dfs(int node, vector &vis, vector adj[], stack &st) { vis[node] = 1; for (auto it : adj[node]){ if (vis[it.first] == 0){ dfs(it.first, vis, adj, st); } } st.push(node); } vector shortestPath(int N, int M, vector &edges) { vector adj[N]; for (auto it : edges) { adj[it[0]].push_back({it[1], it[2]}); } // step 1 do a topo sort stack st; vector vis(N, 0); for (int i = 0; i < N; i++) { if (vis[i] == 0) { dfs(i, vis, adj, st); } } // step 2 take the node out of the stack and relax the edges vector dis(N, INT_MAX); dis[0] = 0; while (!st.empty()) { int node = st.top(); int distance = dis[node]; st.pop(); for (auto it : adj[node]) { if(distance!=INT_MAX) dis[it.first] = min(dis[it.first], distance + it.second); } } // Handling unreachable vertices for (int i = 0; i < N; i++) { if (dis[i] == INT_MAX) { dis[i] = -1; } } return dis; } };

[@nextnotification9857]

understood after 3 hours

[@vaibhavs2740]

Hey striver, you were supposed to give us the intuition but seems like you don't understand the topic well enough yourself. This would give WA in cases when the first element in the TOPO stack is not the source node. Then it's initial dis would be INF and we'd proceed to fill other dis using it. Pop all the stack elements, until you reach the source node. Source node should be the first element in the stack, had it been this way.

[@amansharma4358]

Why Can't we use the same approach we used for undirected graph?

[@varunakrishnani7688]

Understood sir! 😊 Thank you!! 🙏🏻

[@sudiksha586]

,,amazing explanation thank you striver :)

[@shantipriya370]

can we use Dijkstra's Algorithm for this problem?

[@alienx2367]

By using Kahn's algorithm ... if any one needs class Solution { public: vector shortestPath(int N,int M, vector& edges){ queue Queue; vector indeg(N,0); vector adj[N]; for(int i=0;i

[@SatyamEdits]

cannot find this question anywhere.....why...?????? Please provide the link......

[@deveshnandan323]

Expected Space complexity is O(N) then making adj[] list wouldn't make space complexity more ?

[@shivanshsingh176]

Just a traversal void dfs(int src, vector adj[], vector &path, int cost){ path[src] = min(path[src], cost); cost = path[src]; for(auto &itr:adj[src]) dfs(itr.first, adj, path, cost+itr.second); } vector shortestPath(int N,int M, vector& edges){ vector adj[N]; for(vector edge:edges) adj[edge[0]].push_back({edge[1], edge[2]}); vector path(N, INT_MAX); path[0] = 0; dfs(0, adj, path, 0); for(int i=0 ; i

[@tasneemayham974]

AAMMAZZINGG EXPLANATTTIONNN STRIVERRR!!!

[@chaitanyaamajala2582]

Can some one explain why we used toposort for finding distance i mean what is the significance of

[@parthapratik7887]

doubt, is it necessary that top of stack will be source node ??

[@aesthetich9730]

Same doubt

[@imajt5]

@@aesthetich9730 the answer, That is pop the elements of the stack until we obtain the source node , Because the element above the source node in the stack cannot be travelled with the element below to it

[@achrafBadiry]

Intuition of why use topological sort 23:08

[@manoj-vr9yi]

hey,i had a doubt in case we are taking int max ,wouldn't it will try to sum weights in int max which will give an error in case of component.@everyone

[@hashcodez757]

MUST READ☠☠ What if we apply the Kahn's Algorithm? => there has to be an extra check, but why? DFS-based Topological Sort (in your second code): The topological order is constructed using DFS. In DFS, when a node finishes all of its descendants (children), it is pushed onto the stack, ensuring that all dependencies of a node are processed before the node itself. When you pop nodes from the stack for edge relaxation, they are guaranteed to be processed after all their dependencies, so there’s no need to check if the node is reachable before relaxing its edges. This order guarantees that nodes are relaxed only when their predecessors have already been processed. Kahn's Algorithm (BFS-based Topological Sort) (in the first code): In Kahn’s algorithm, you process nodes with zero indegree first and then reduce the indegree of their neighbors. The BFS-style processing works in layers (starting with the source nodes), but it doesn't guarantee that a node will only be processed if its predecessors are reachable. Because Kahn’s algorithm processes nodes without directly considering whether the node itself has been reached, we need an explicit check (i.e., dist[it] != INT_MAX) before relaxing the edges of that node. Why the DFS-based Code Works Without an Extra Check: In your DFS-based topological sort, the nodes are processed in the exact reverse of their dependencies: If a node A depends on node B (i.e., there is an edge from B to A), then B will be processed before A during the DFS traversal. This means that by the time you process node A in the relaxation step, node B has already been fully processed. Thus, if A is unreachable, it’s guaranteed that its predecessors are also unreachable, and you won't relax any edges from an unreachable node. In contrast, the BFS-based topological sort processes nodes as soon as their indegree becomes zero, without checking if they are reachable from the source. That's why you need an explicit check to avoid relaxing edges from unreachable nodes in Kahn’s algorithm. Summary: DFS-based topological sort naturally handles the order of dependencies and only processes nodes after their dependencies are processed, so no extra check is needed for reachability during relaxation. BFS-based topological sort (Kahn's algorithm) doesn't guarantee that a node is reachable before it is processed, so you need to explicitly check if the node has been reached (dist[it] != INT_MAX) before relaxing its edges. Both algorithms are correct, but DFS topological sorting avoids the need for an extra reachability check due to the natural order in which nodes are processed. CODE class Solution { private: vector topoSort(int V, vector adj[]) { // code here vector indegree(V,0); queue q; for(int i=0;i

[@Vamshi_krishna568]

why can't use BFS instead of topo sort because BFS will be traverse same equal as toposort did!

[@lakshsinghania]

Modified code as per GFG: //{ Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends // User function Template for C++ class Solution { private: void toposort(int node, vector adj[], stack& st, vector& vis) { vis[node] = 1; for (auto it : adj[node]) { int v = it.first; if (!vis[v]) toposort(v, adj, st, vis); } st.push(node); } public: vector shortestPath(int N, int M, vector& edges) { // make the graph vectoradj[N]; for (int i = 0; i < M; i++) { int u = edges[i][0]; int v = edges[i][1]; int wt = edges[i][2]; adj[u].push_back({ v,wt }); } // step1: Perform the topological Sort vector < int > vis(N, 0); stack < int > st; for (int i = 0; i < N; i++) if (!vis[i]) toposort(i, adj, st, vis); // Step 2:- Relax all the edges // mk the dist arr vector < int > dist(N, 1e9); as 0 is the src dist[0] = 0; while (!st.empty()) { int node = st.top(); st.pop(); for (auto it : adj[node]) { int v = it.first; int wt = it.second; if (dist[node] + wt < dist[v]) dist[v] = dist[node] + wt; } } for (int i = 0; i< N;i++) if (dist[i] == 1e9) dist[i] = -1; return dist; } }; //{ Driver Code Starts. int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector edges; for(int i=0; ix; temp.push_back(x); } edges.push_back(temp); } Solution obj; vector res = obj.shortestPath(n, m, edges); for (auto x : res) { cout