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
Thanks a lot, striver. Ur content is far better than paid courses. U literally explained us everything in such a depth. Thanks again for all your amazing playlists.
I just love the confidence and the clarity with which you code the solution. I have started to recite the solution similar to your style while coding alone ^^
This question is updated on GFG , if you look at strivers screen its just asking path but in updated question you need to append the dist[n] also and then reverse
just do - reverse(path.begin(), path.end()); // Insert the total distance as the first element of the result path.insert(path.begin(), dist[n]); return path;
we can print the path with the help of distance array only (no need of parent array) if(dis[n]==1e9){ return {-1}; } vectorans; int curr_node=n; while(curr_node!=1){ ans.push_back(curr_node); for(auto it:al[curr_node]){ if(dis[it.first]==dis[curr_node]-it.second){ curr_node=it.first; } } } ans.push_back(1); reverse(ans.begin(),ans.end()); return ans;
Hi sir, I solved this question by own and this is happened because of you. Before your videos graph is like impossible thing for me but now I can solve medium level questions easily
Hi Striver, With your hint I was able figure out that this algo is same as we used to print LIS/LCS in DP. Can't think of anyone teaching DSA better than you. Well its not wrong to say that you are the Netflix of DSA xD
My approach similar to WordLadder-2, in set along with dist store currentList too... vector shortestPath(int n, int m, vector& edges) { // Code here vector adj[n+1]; for(int i=0; i
Another short approach using Dijkstra's Algorithm (in this we will store the path in priority queue itself just like word ladder II) vector shortestPath(int n, int m, vector& edges) { vector adj[n + 1]; for(auto e : edges) adj[e[0]].push_back({e[1], e[2]}), adj[e[1]].push_back({e[0], e[2]}); vector d(n + 1, INT_MAX); d[1] = 0; priority_queue pq; pq.push({0, {1}}); int minD = INT_MAX; vector ans = {-1}; while(pq.size()) { vector path = pq.top().second; int dis = pq.top().first; pq.pop(); int node = path.back(); if(node == n && minD > dis) minD = dis, ans = path; for(auto ad : adj[node]) { if(d[node] + ad.second < d[ad.first]) { d[ad.first] = d[node] + ad.second; path.push_back(ad.first); pq.push({d[ad.first], path}); path.pop_back(); } } } return ans; }
Question is updated in GFG, it is undirected so we need to add u->v and v->u both in the adjacency List. Also Need to add the dist[n] to the path and need to reverse it as the question is asking the dist and path of src to N node.
We can also use pq of dist and the path we have so far to solve it without needing the parent array. vector shortestPath(int N, int m, vector& edges) { priority_queue pq ; vector dist(N+1,INT_MAX) ; vectoradj[N+1] ; 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}) ; adj[v].push_back({u,wt}) ; } pq.push({0,{1}}) ; //bool flag = false ; while(!pq.empty()) { auto x = pq.top() ; pq.pop() ; vector path = x.second ; int node = path.back(); int dis = x.first ; if (node==N) { // flag = true ; return path ; } for (auto x : adj[node]) { int adjNode = x.first ; int adjDis = x.second ; if (dist[adjNode]>adjDis+dis) { dist[adjNode] = adjDis + dis ; path.push_back(adjNode); pq.push({adjDis + dis, path}); path.pop_back(); } } } return {-1} ; }
Was able to come up with the solution without watching the video. Here's my implementation : vector shortestPath(int n, int m, vector& edges) { // Code here vectoradj[n+1]; for(int i = 0 ; i < edges.size() ; i++){ adj[edges[i][0]].push_back({edges[i][1],edges[i][2]}); adj[edges[i][1]].push_back({edges[i][0],edges[i][2]}); } priority_queue pq; pq.push({0,{1,{1}}}); vectordist(n+1,INT_MAX); dist[1]=0; while(!pq.empty()){ pair ki=pq.top(); pq.pop(); int dis=ki.first; int k=ki.second.first; vectorvec=ki.second.second; vectorvy=vec; if(k==n) return vec;
for(int i = 0 ; i < adj[k].size() ; i++){ if(dis+adj[k][i][1]
Understood Suggestion:- ek sath itne sare video mat upload karo channel ke reach Kam hoti hai Ho sake to ek ek hour ke video schedule kardo And amazing approach striver Bhai 😀 Edit:- mai galat tha #keep_striving
hey Striver bhaiya, i have a doubt that instead of storing the parents, can't we do this. if anyone else can help , then please. int node = n; while(node != 1){ for(auto it : adj[node]){ int adj_node = it.first; int adj_wt = it.second; if(dist[node] == dist[adj_node] + adj_wt){ ans.push_back(adj_node); node = adj_node; } } } intution is simple that whose adjNode's distance + weight gives the node's distance will be the parent node.
No it's based on graph If you want smallest path (or) all paths then store parent=list of set of values Ex:parent=[0,{1, 2}] dist=[0,1] Again if we get dist 1 of index 1 from other path then simply add that node to parent [1] then apply dfs not while loop.
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java ) because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
Hey instead of using extra array of parent can't we store a Pair in the dist array itself and do the backtrack from there. This way we can save some space.
How can it have a better time complexity?, If observed closely the total number of integers will be equal, so I don't think it's better from any angle.
hey striver , I solved this problem using a different approach where my pq consists of distance and vector(containing path until now) runs just fine class Solution { public: vector shortestPath(int n, int m, vector& edges) { // Code here vectorans; vectoradj[n+1]; for(int i=0;i
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
understood Even if my result and expected result is same its not passing test case. Test case number - 63 pin this comment so everyone can save their time Your Code's output is: 1 46 11 51 It's Correct output is: 1 46 11 51 Output Difference 1 46 11 51
As the note not yet updated. Just for resource : java code public static List shortestPath(int n, int m, int edges[][]) { ArrayList adj = new ArrayList(); for(int i = 0;i
I've understood the algo and the code but it's showing TLE error in gfg for last 2 cases, both with priority_queue and set...anyone else having same problem as me ?
why we need to push 5 at the end to run this code on gfg vector shortestPath(int n, int m, vector& edges) { vector adj[n+1]; for(auto it:edges){ adj[it[0]].push_back({it[1],it[2]}); adj[it[1]].push_back({it[0],it[2]}); }
Because they asked for the shortest distance value as well. So, they want you to first give them the shortest distance as the first index then the graph path.
![OhGeesy x Lefty Gunplay - What It Iz [Official Music Video]](http://i.ytimg.com/vi/L0yzW9t2ixk/mqdefault.jpg)
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
Solved this code without watching any approach in this video just when he said try it out first, i go and solved it. Thanks Striver.
Thanks a lot, striver. Ur content is far better than paid courses. U literally explained us everything in such a depth. Thanks again for all your amazing playlists.
I just love the confidence and the clarity with which you code the solution. I have started to recite the solution similar to your style while coding alone ^^
This question is updated on GFG , if you look at strivers screen its just asking path but in updated question you need to append the dist[n] also and then reverse
yeah, i was confused where's the error in my code , then did this and passed all tetscases. Thanks!!
Thanks for sharing 👍
just do -
reverse(path.begin(), path.end());
// Insert the total distance as the first element of the result
path.insert(path.begin(), dist[n]);
return path;
@@prakharm614 thanks buddy if u dont mind can you give me ur discord...
💫
Thanks a lot was confused about this!!!
we can print the path with the help of distance array only (no need of parent array)
if(dis[n]==1e9){
return {-1};
}
vectorans;
int curr_node=n;
while(curr_node!=1){
ans.push_back(curr_node);
for(auto it:al[curr_node]){
if(dis[it.first]==dis[curr_node]-it.second){
curr_node=it.first;
}
}
}
ans.push_back(1);
reverse(ans.begin(),ans.end());
return ans;
Hi sir, I solved this question by own and this is happened because of you. Before your videos graph is like impossible thing for me but now I can solve medium level questions easily
simple solution again.. thanks Striver. This Graph series feels easier than any other..❤
Solved this without watching the video. Took 2 hours but was worth it.
Using that parent array was indeed a smart move 😀 !!
Understood! Such a wonderful explanation as always, thank you very much!!
Hi Striver, With your hint I was able figure out that this algo is same as we used to print LIS/LCS in DP. Can't think of anyone teaching DSA better than you. Well its not wrong to say that you are the Netflix of DSA xD
same same
which year?
And I solved it seeing ur hint (print LIS problem in dp)
@@krishanpratap3286 2020 passed out lol
So are you looking to switch?
after line 20 we should push pair {0,1} initially to priority queue
you can but here we push {0,1} as we store in pq and we store in adj list hope you get this
My approach similar to WordLadder-2, in set along with dist store currentList too...
vector shortestPath(int n, int m, vector& edges) {
// Code here
vector adj[n+1];
for(int i=0; i
Another short approach using Dijkstra's Algorithm (in this we will store the path in priority queue itself just like word ladder II)
vector shortestPath(int n, int m, vector& edges) {
vector adj[n + 1];
for(auto e : edges) adj[e[0]].push_back({e[1], e[2]}), adj[e[1]].push_back({e[0], e[2]});
vector d(n + 1, INT_MAX);
d[1] = 0;
priority_queue pq;
pq.push({0, {1}});
int minD = INT_MAX;
vector ans = {-1};
while(pq.size()) {
vector path = pq.top().second;
int dis = pq.top().first; pq.pop();
int node = path.back();
if(node == n && minD > dis) minD = dis, ans = path;
for(auto ad : adj[node]) {
if(d[node] + ad.second < d[ad.first]) {
d[ad.first] = d[node] + ad.second;
path.push_back(ad.first);
pq.push({d[ad.first], path});
path.pop_back();
}
}
}
return ans;
}
damn nice 🔥
Great soln!!
same approach but tle on tc 4
GFG Apparantly have updated the testcases and this solution no longer is getting accepted
you just have to append the shortest path distance at the beginning of the answer array
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Just love ur way of solution Problem ❤️❤️
*Problem Solution
NOTE
Now the question is updated ,we also have to pushback the weight of shortest path.
typedef pair pip;
vector shortestPath(int n, int m, vector& edges) {
vector< pair >adj[n+1];
for(auto &it : edges)
{
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue< pip, vector , greater< pip > >pq;
pq.push({0,1});
vectordist(n+1,1e9);
dist[1] = 0;
vectorparent(n+1);
for(int i = 1;i 0)
{
auto it = pq.top();
int node = it.second;
int dis = it.first;
pq.pop();
for(auto &it : adj[node])
{
int adjnode = it.first;
int edgeweight = it.second;
if(dis + edgeweight < dist[adjnode])
{
dist[adjnode] = dis + edgeweight;
pq.push({dis+edgeweight , adjnode});
parent[adjnode] = node;
}
}
}
if(dist[n] == 1e9) return {-1};
vectorpath;
int node = n;
while(parent[node] != node)
{
path.push_back(node);
node = parent[node];
}
path.push_back(1);
path.push_back(dist[n]);
reverse(path.begin(),path.end());
return path;
}
it's showing tle error in the last test case
Thank you so much!!! Was struggling to find my mistake!
@@bhaktisharma9681 did u find the solution ?? Then pls share it here 🙏
Can you explain the code for graph creation? I'm not able to understand it
@@vaisakh5802 Watch initial videos of the series and understand how adjacency list maintains its adjacent nodes and weight
Question is updated in GFG, it is undirected so we need to add u->v and v->u both in the adjacency List.
Also Need to add the dist[n] to the path and need to reverse it as the question is asking the dist and path of src to N node.
TreeSet solution in Java (Just need to override compareTo, equals and hashCode methods of the SortedSet interface):
class Pair implements Comparable{
int node, dist;
public Pair(int dist, int node){
this.node = node;
this.dist = dist;
}
@Override
public boolean equals(Object e){
Pair other = (Pair) e;
return node == other.node;
}
@Override
public int hashCode(){
return node;
}
@Override
public int compareTo(Pair p){
if(p.dist == this.dist)
return this.node - p.node;
return this.dist - p.dist;
}
}
class Solution
{
static int[] dijkstra(int V, ArrayList graph, int S)
{
//dist, node -> sort by smaller distance from src. If dist same, then sort by smaller node
TreeSet set = new TreeSet();
set.add(new Pair(0, S));
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[S] = 0;
while(!set.isEmpty()){
Pair cur = set.pollFirst();
int src = cur.node, distToSrc = cur.dist;
for(ArrayList edge : graph.get(src)){
int dest = edge.get(0), curDist = edge.get(1);
if(dist[dest] > distToSrc + curDist){
dist[dest] = distToSrc + curDist;
set.add(new Pair(dist[dest], dest));
}
}
}
return dist;
}
}
Please use a proper compiler which shows output also so it will be more understandable.
We basically hashing the node for each updatation in the distances[adjNode]. I guess we can use HashMap too in this case.
one major doubt. How can we come up with these kind of solutions on our own???
Practice, and practice...
because if you just keep practicing with closed eyes it would take an eternity to become a good problem solver.....
@@SatyamEdits Thank you
@@takeUforward Thank you
Aa jata hai bro if you practice many questions
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
🤣😂
what if we need to find all the shortest paths from src to destination? (eg if there are 3 paths from src->dest with total wt=5,how to get all three)
We can also use pq of dist and the path we have so far to solve it without needing the parent array.
vector shortestPath(int N, int m, vector& edges) {
priority_queue pq ;
vector dist(N+1,INT_MAX) ;
vectoradj[N+1] ;
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}) ;
adj[v].push_back({u,wt}) ;
}
pq.push({0,{1}}) ;
//bool flag = false ;
while(!pq.empty()) {
auto x = pq.top() ;
pq.pop() ;
vector path = x.second ;
int node = path.back();
int dis = x.first ;
if (node==N) {
// flag = true ;
return path ;
}
for (auto x : adj[node]) {
int adjNode = x.first ;
int adjDis = x.second ;
if (dist[adjNode]>adjDis+dis) {
dist[adjNode] = adjDis + dis ;
path.push_back(adjNode);
pq.push({adjDis + dis, path});
path.pop_back();
}
}
}
return {-1} ;
}
What if there are multiple shortest path and we have to print all of them? In that case what should we do?
Masterpiece Explanation
Was able to come up with the solution without watching the video. Here's my implementation :
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectoradj[n+1];
for(int i = 0 ; i < edges.size() ; i++){
adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});
adj[edges[i][1]].push_back({edges[i][0],edges[i][2]});
}
priority_queue pq;
pq.push({0,{1,{1}}});
vectordist(n+1,INT_MAX);
dist[1]=0;
while(!pq.empty()){
pair ki=pq.top();
pq.pop();
int dis=ki.first;
int k=ki.second.first;
vectorvec=ki.second.second;
vectorvy=vec;
if(k==n) return vec;
for(int i = 0 ; i < adj[k].size() ; i++){
if(dis+adj[k][i][1]
almost same type of solution but got tle on case 4
Understood
Suggestion:- ek sath itne sare video mat upload karo channel ke reach Kam hoti hai
Ho sake to ek ek hour ke video schedule kardo
And amazing approach striver Bhai 😀
Edit:- mai galat tha
#keep_striving
Areh pdhai ki channel ki reach hoti v nai h, word of mouth pe hi chalta h
@@takeUforward true
@@takeUforward still if u upload 1 or 2 video daily that will make us consistent
Litterly saved me, deserves a subscription if you ask me!!!
how to handle multiple shorest path . This question was asked in my college intership OA of atlassian. PLss tell how to handle ?
I am unable to find this Question on GFG
Same
TLE on the last test case?
Understood! amazing Explanation.
understood, thanks for the great video
Thank you sir 🙏
Understood sir thankyou❤✨🙏🙇♂
Huge effort 🤩
Hi striver, can the datatype of distance array be a class which stores node distance and parent ? so that we will not take two separate arrays?
Thank you very much. You are a genius.
if the weight of both edges is same, we need to handle that based on nodes in Priority Queue
understood, thank you so much.
Understood ❤
hey Striver bhaiya, i have a doubt that instead of storing the parents, can't we do this.
if anyone else can help , then please.
int node = n;
while(node != 1){
for(auto it : adj[node]){
int adj_node = it.first;
int adj_wt = it.second;
if(dist[node] == dist[adj_node] + adj_wt){
ans.push_back(adj_node);
node = adj_node;
}
}
}
intution is simple that whose adjNode's distance + weight gives the node's distance will be the parent node.
Understood Bhaiya
Sir you forgot the case of returning list of -1s if path's not possible
UNDERSTOOD.
just amazing !!
Understood!
Understood 👍
Very much helpful 😍😍
what about no path case (-1)?
What if there are two shortest path 1->2->4->5 and 1->3->5 with the same dist value , will it print 1->3->5?
No it's based on graph
If you want smallest path (or) all paths then store parent=list of set of values
Ex:parent=[0,{1, 2}] dist=[0,1]
Again if we get dist 1 of index 1 from other path then simply add that node to parent [1] then apply dfs not while loop.
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
doesn't matter what you store at the parent caue when you will get the path it will automatically get updated with the new parents.
Understood
Thank you bhaiya
Hey instead of using extra array of parent can't we store a Pair in the dist array itself and do the backtrack from there. This way we can save some space.
#tuf and take forward for crowdwork...#leetcode more solution needed
How can it have a better time complexity?, If observed closely the total number of integers will be equal, so I don't think it's better from any angle.
lol, pair of size n is nothing but two arrays of size n clubbed together.
Understood 😇
we dont have to initialize the whole parent array, just do parent [source] = source ;
hey striver , I solved this problem using a different approach where my pq consists of distance and vector(containing path until now) runs just fine
class Solution {
public:
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectorans;
vectoradj[n+1];
for(int i=0;i
understood bhaiya
UNDERSTOOD
adj[it[0]] is a pair, how can we do a push_back to a pair??
nice:) explanation sir
Golden❤
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
why cant we take max priority queue? its giving tle .
Huge love from south❤
understood💙💙💙
understood
UnderStood Sir!
THank you
Where can we find the java code for this video
understtooooddddd
can someone share link of question , it seems to be broken
i am not able to write code by myself what to do?
amazing
understood!!
My Attempt ->
vector shortestPath(int n, int m, vector& edges) {
vector adjList(n+1);
vector distances(n+1,{INT_MAX,vector{}});
distances[1] = {0,{1}};
for(int i=0;i distances[node].first) continue;
vector path = distances[node].second;
for(auto pair : adjList[node]){
int adjNode = pair.first;
int d = pair.second;
if(distances[adjNode].first > d + dist) {
distances[adjNode].first = d + dist;
vector newPath = path;
newPath.push_back(adjNode);
distances[adjNode].second = newPath;
pq.push({d + dist, adjNode});
}
}
}
vector result;
if(distances[n].first == INT_MAX) return {-1};
else {
result.push_back(distances[n].first);
for(auto node : distances[n].second) result.push_back(node);
return result;
}
}
am i missing something?
since its undirected graph there definitely exists a path right?
then y print (-1)
What if the Node is Unreachable ?
@@gamerversez5372 undirected graph means it's reachable every where.
Also there is only one component
awesome
its 3:54 am and busy creating my future😁😄
understood
sir
understood
Even if my result and expected result is same its not passing test case. Test case number - 63
pin this comment so everyone can save their time
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
same here
glitch hai, ab working
what if path doesn’t exist?
For same code but using unordered map insted of vector for getting path is giving me tle on 7th testcase itself😮!! Can anyone tell me the reason
i was not able to solve it after pausing, what should I do. Am i that much incompetent.
Would you please send me problem link
i can feel u bro, i'm also feeling same but only solution is practice
As the note not yet updated.
Just for resource : java code
public static List shortestPath(int n, int m, int edges[][]) {
ArrayList adj = new ArrayList();
for(int i = 0;i
Please provide main.cpp code.
I've understood the algo and the code but it's showing TLE error in gfg for last 2 cases, both with priority_queue and set...anyone else having same problem as me ?
Yes, I solved it alone and got TLE using Java. But when I solved it using C++ it ran well!!
“understood”
why we need to push 5 at the end to run this code on gfg
vector shortestPath(int n, int m, vector& edges) {
vector adj[n+1];
for(auto it:edges){
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue pq;
vector dist(n+1,1e9);
vector parent(n+1);
for(int i=1;i
Because they asked for the shortest distance value as well. So, they want you to first give them the shortest distance as the first index then the graph path.
Please anyone tell me from where could I learn the use of priority queue of min heap in java
gfg
understood :)
its giving TLE for test case 64
Hey! Use set method it would work , I also got TLE with python but as number of iterations could be a problem so use set method
@@mohdaman7228 thankss
Can anyone explain Line 19: Initializing parent array equal to the index value ?? @16:06
this is done because we need to stop after node 1 is reached . The condition used inside while(parent[node]!=node) will become false for node 1.
showing (SIGABRT) on last 2 test cases, anyone?