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
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
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)
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.
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...
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.
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
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; } };
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.
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
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 ?
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
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.
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.
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];
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
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; } }
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); } }
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);
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.
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
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 .
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.
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
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?
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 🥲🥲🥲
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
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)
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
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.
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.
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
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
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; } };
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.
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
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; } };
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
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.
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
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
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
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
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
coded in bfs //{ Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends // User function Template for C++ class Solution { private: public: vector shortestPath(int N, int M, vector& edges) { // make the graph vector 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 }); } // Step 1: Perform the topological Sort using BFS vector inDegree(N, 0); for (int i = 0; i < M; i++) { int u = edges[i][0]; int v = edges[i][1]; inDegree[v]++; } queue q; for (int i = 0; i < N; i++) { if (inDegree[i] == 0) { q.push(i); } } vector dist(N, 1e9); dist[0] = 0; while (!q.empty()) { int node = q.front(); q.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; } inDegree[v]--; if (inDegree[v] == 0) { q.push(v); } } } 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
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
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 disconnected component the source will not be connected to any one of the node in it. So travelling through all the nodes in the same connected component is enough
@@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
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.
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]
*JAVA CODE USING SIMPLE DFS TECHNIQUE* class Pair{ int end , edge; Pair(int e , int ed){ end = e; edge =ed; } } class Solution { public int[] shortestPath(int N,int M, int[][] a) { int ans[] = new int[N]; List list = new ArrayList(); for(int i=0;i
In this video the first node of topo sort is cleverly assumed to be the source? what if the source was zero and top sort gives 6 as the first node? how will the relaxation of edges work?
In this case our src node and the first node of toposort were the same what happens when those are diff. More precisely in above case we had dist[6] = 0 as it was our source. but lets assume 6 wasnt our source then dist[6] = INF, Then would we determine dist[] using above algo?
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
thnks a lot for this amazing content. understood🙂🙂
Thanks for such a great series 😃
understood
understood
understood😄
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
Thanks for this!!!
Thank you
This needs to be pinned. I could've saved 20 minutes
Thanks for this. Got fully confused by the example.
defenetely an underrated comment the examples will make u think this through btw ... thanks for this
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)
Much much thanks for this , thinking about the same thing for last 3 days.
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
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.
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...
Thanks I was wondering about that
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.
u don't know how much u have made graph easy for a naive coder like me!
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
i did'nt understand why this and next question can't be done using Dijkstra's algo? could you please explain?
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;
}
};
Yes I told him to update it. Kese nai karega 😉
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.
Thanks man🤝
what is 1e9?
@@DevanshuAugusty pow(10,9);
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
thanks so much, got stuck there
thanks bro
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 ?
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
thanks
i did'nt understand why this and next question can't be done using Dijkstra's algo? could you please explain?
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.
Insightful Ma,n!!.
It works...thanks.
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
Nice observation man
Nice observation
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
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.
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
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
This should be the top comment, surprised how no one is noticing this issue
Exactly Striver Should pin this
thanks, finally understood it
I have been thinking for 3 hours, that how striver got that, but finally after seeing to your comments relaxed, thanks bhai doubt resolved..
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;
}
}
Helpful. Thanks.
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);
}
}
Or just check at the end (before returning), if any value of distance == 1e9 and replace it with -1.
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);
@@sg627k what is 1e9
thanx man
@@DevanshuAugusty 1x10^9
I have seen a lot of Graph playlists but this is on some next level. After watching this my all concepts are cleared.
Thank you striver for clear explanation and also adding such stack over flow posts , it improves the learning experience.
where is the link to the stackoverflow post?
@@rickk3300 I too cannot see it.
Neeku acakada kanipinchindi ey aa link
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.
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
Understood. You are an awesome mentor/tutor. What an explaining skills you have . Great job Striver.🤗
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 .
Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thank you @striver for helping us in logic building and making the tougher problems like a piece of cake
He has god level explanation skills.
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.
1014/1121 passed after that i got TLE
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
@@dank7044 You are right.
Can you kindly add timestamps for imp stuffs like intuition, code ,Time complexity and stuffs in the description..
Such a simple explanation, Understood!
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?
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 🥲🥲🥲
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
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)
Yeah! Dist for nodes before source in toposort should be inf only
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
Kya samjhaya hai 👏👏👏
Understood.
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.
The question has been modified just add this snippet in the end
for(int i=0; i
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.
your code is super simple to understand
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
why we can't take INT_MAX
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
@@39_jatinjain4 INT_MAX can overflow during calculation of distances
best graph playlist ever
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;
}
};
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;
}
🙂
Understood! What an amazing explanation as always, thank you very much!!
This is gold!!
great intuition yet simple
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.
what if stack top is not equal to source?
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
@@ganeshvernekar2797 thanks bruh 🙌
@@ganeshvernekar2797 Thanks you Ganesh bhai you clear my doubt as well
@@ganeshvernekar2797👏👏👏
i wish i could explain like you in the interviews
Thank you So much Striver !
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;
}
};
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?
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
Great man that's what I have been looking for
Thank you, Striver 🙂
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.
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
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
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
@@gsmdfaheem will check out, thanks for pointing out.
@@breakthecode8323 no problem
Understood sir! 😊
Thank you!! 🙏🏻
Understood sir thankyou so much🙇♂🙏🙏❤
Nicely explained
in this case to perform the toposort, you can call dfs only for the starting node.
really impressive approach
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
,,amazing explanation thank you striver :)
really loved explaination
can anyone share me the link of this question?? i cant open up the link in the description :/
understood, thanks for the great video
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
Understood Striver❤
Intuition 23:00
coded in bfs
//{ Driver Code Starts
// Initial Template for C++
#include
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution {
private:
public:
vector shortestPath(int N, int M, vector& edges) {
// make the graph
vector 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 });
}
// Step 1: Perform the topological Sort using BFS
vector inDegree(N, 0);
for (int i = 0; i < M; i++) {
int u = edges[i][0];
int v = edges[i][1];
inDegree[v]++;
}
queue q;
for (int i = 0; i < N; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
vector dist(N, 1e9);
dist[0] = 0;
while (!q.empty()) {
int node = q.front();
q.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;
}
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
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
Understood 💯💯💯
AAMMAZZINGG EXPLANATTTIONNN STRIVERRR!!!
where's the stack over flow link ?
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
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 disconnected component the source will not be connected to any one of the node in it.
So travelling through all the nodes in the same connected component is enough
Thanks man..for everything
Do the topo short, Take node out and keep updating the distances.
if topo sort's first element is different from src then ?
I uses Dijsktra algorithm for DAG and it works fine
But time complexity is high
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
Very nice !! Really love it :)
Intuition of why use topological sort 23:08
simply awesome
doubt, is it necessary that top of stack will be source node ??
Same doubt
@@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
understood striver
understood sir🙇♂🙇♂🙇♂
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
Thank you sir
understood
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;
}
};
Shouldn't that adj declaration be vector< vector< pair> > adj (N); ??
this will work too,but striver actuallt declared an array,where each el is vectro
Great explaination
I need to do it again.
What's the need to do the TOPO sort first?
I think we can do it simply without topo sort as well???
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.
some nodes where value of dis < 0 , are the nodes that cannot be reached
no need to do this,code works normally too,just initiate your vec with a large val
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]
*JAVA CODE USING SIMPLE DFS TECHNIQUE*
class Pair{
int end , edge;
Pair(int e , int ed){
end = e;
edge =ed;
}
}
class Solution {
public int[] shortestPath(int N,int M, int[][] a) {
int ans[] = new int[N];
List list = new ArrayList();
for(int i=0;i
understood after 3 hours
Understood! :)
Thank you for your invaluable efforts striver! _/\_ ^^
Is the topological sort necessary? Can't we just apply normal BFS starting from the source node?
yes you can apply BFS or djekstra.
We cannot apply simple BFS here because edge weights are not same
understood ❤
In this video the first node of topo sort is cleverly assumed to be the source?
what if the source was zero and top sort gives 6 as the first node?
how will the relaxation of edges work?
Understood ❤️
very good question
Understood 👍
In this case our src node and the first node of toposort were the same what happens when those are diff. More precisely in above case we had dist[6] = 0 as it was our source. but lets assume 6 wasnt our source then dist[6] = INF, Then would we determine dist[] using above algo?