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
hey bhaiya, i might be wrong but i think it has exponential tc and sc under few circumstances. "like for edge cases" and gfg might have weak test cases
the complexity will be O(V+E*K) and not O(V+E) if the complexity of using a queue was O(E) then why would people use dijkstras which takes a complexity of O((V+E)log(V)).
I did the Dijsktra's same as you showed in the first step. Just tweaked a little, I reversed the edges and then started the Dijsktra's from Destination towards source so that in case there is a path with less cost but more stops towards destination, that will be rejected midway and the path taking more cost but less stops will be considered. Here is the code - class Solution { public: int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { unordered_map graph; for(int i=0;i k) continue; vector connectedNodes = graph[node]; for(int i=0;i newCost) { cost[newNode] = newCost; pq.push({newCost, newStops, newNode}); } } }
This is the best question if you want to understand the inner-workings of both bfs and djikstra and the difference between them, however I feel that this question needed an in depth explanation on why we are doing the specific things that we are doing in both the queue case and the priority queue case.
@Striver at 15:20, we will consider (as per dry run and algorithm) taking the path from 0->3->1 , as the dist would be less from prev stored dist[ 1 ] and also push it in the priority queue. I think it has to be taken because djikstra's will not only give us the the shortest path with valid number of stops to node 2 (dst) but it will also generate shortest path with valid number of stops to all the nodes in graph. So path from 0->3->1 should be the shortest path(dist = 4) which will also be covered under valid number of stops(2) rather than path 0->1 (where dist = 5, stops = 1) Edit: valid number of stops instead of least number of stops
Yes, right there is a slight mistake in the video for this, cost of 4 should be considered instead of 5 from the time 15:15 to 15:20, while calculating this. Hope @Striver will fix this.
Just make sure in the if check you put the condition as (cost + edW < dist[adjNode]) and not (dist[Node] + edW < dist[adjNode]) or else edge case will fail MISCONCEPTION: we can save some space in the queue nd do queue coz distance is already obtainable from dis[ ], so why maintain it specifically in the queue? ANS: no coz in the queue we store the distance coming from a specific parent node ie a particular path , nd that path is used for further exploration when we take it out of the queue nd consider that paths distance ...but there can be other paths as well...dis[ ] can't maintain the paths, it just stores the path with minimum distance, which may not guarantee the path with least stops(which is our top priority)...hence we have to maintain the instance of the distance of a particular node in the queue
this comment is worth the video explanation !!, been stuck on it for a long time. thanks for putting the light in place. Striver content quality -> 100%
An excellent approach to this problem. I had solved this same problem using pq and maintaining minimum cost to reach every node within each number of stops upto k, and it had worked but your solution has a way better tc and sc.
replace a condition if(curCityStop > k) continue; with below line if(curCityStop > k) break; because their is no need to proceed further as all further node will have stops > k #best content in youtube #striver
I don't understand why people find this problem confusing. Sure, it can be solved with a priority queue, but since the number of stops increases by one at each step, using a regular queue can help reduce the time complexity somehow. Another important point is that we're using the number of stops as the main criterion. If you reach a destination with a smaller distance but more stops, it's not useful. Therefore, it's better to prioritize routes with fewer stops first. Even after that, we still check routes with more stops, but only if the number of stops is within the allowed limit (≤ k). In such cases, we store those routes as well.
At 15:26 We will consider (1,3,2) with stop=1,node=3,cost=2. This is pointing to 1 with cost +2, so we will get (2,1,4) and append it to the P-Queue. In next iteration we will pop (2,1,4) ,with stop=2,node=2cost=4,that is the minimum from heap. This pointing to node 5 with cost +5 and will give(3,2,9) and to node 4 with cost +1 and will give(3,4,5). Since we reached 2 with better cost of 9 we will update it from 10 to 9. and append both (3,2,9) and (3,4,5) to the PQ. Now, we will pop (2,4,6) with stop=2,node=4,cost=6 (from 2nd iteration). This is pointing to node 2 with cost +1 and we will get (3,2,7). Again we reached node 2 with lesser cost of 7 within 3 stops. This is the most minimum we could go. As all the element left in PQ are having more stops. Hence, Striver is always right, just he missed something for which he already made us ready. Waiting for tomorrow. 7/08/2024 for TUF+.
Dijkstra with PQ will also work, just don't push the value inside the queue, if value of stops > k, because we are sure that, it won't yield us the ans.
I tried with PQ but it will fail in below case if we don't put the value in the queue if value of stops > k, [[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]] src = 0 and dst = 2 k =2 The PQ will give ans = 9 but it should be 7
@@vm1662 No, it will work(sharing the code) class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { //making graph ArrayList adj=new ArrayList(); for(int i=0;i
1.Make Adj List and Distance Vector. 2.Push Src Node into queue. 3.move levelwise and increment cnt on each level. 4.when you rech dest and your count is k then break it and return distance.
I feel that the part which needs more attention is quickly skipped and some basic stuff which is quite intuitive is over stretched. Not sure whether everyone understood the correct reason to make a queue of stops, nodes and distance and not a priority queue of distance, nodes and stops
true, he should have explained more on why we do consider even larger distance paths in the case of djikstra as long as it is a valid one and push it back as compared to bfs where we don't need to do so. In the bfs, it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
@@saumyaranjan9256 hi, confused here regarding your bfs explanation, lets take 2 paths, 3->4->1 and 3->5->6->1, suppose path 1 has 40 as distance and path 2 has 20 as distance, "it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
@@kushalkollu8628Just image if you are starting from node 0 - - >3 and between 3 - - 4 there will be extra node but with small distance. So if you take priority Queue with distance, The node 4 will never be accessed by node 1 even if it have sufficient stop.
@@rohitkumaramNo the prioritizing will be in priority queue not in the mindistance array he should include that too in the priority queue but anyway the answer will be same
This was the some level good problem bhaiya which forced us to think why simply we can not use dijkstra algorithm and also normal queue can be used to solve the problem.
Thanks Striver, I had tried this question before and was trying to do a priority queue but with few added conditions as per checking distances and both stop, though that had worked but was very time consuming solution. This one is much faster and without priority queue which totally makes more sense.
While deciding to insert in priority queue, we need to sort by lowest cost and keep a check to see if cost is greater, atleast number of stops are less or not.
I see some of the comments were they are mentioning that we can omit the cost variable from the queue and take it from the distance[]. Well, that will not work. Let me tell you why: 1. Two different paths to the same node can have different numbers of stops. In some cases, a path with more stops may offer a cheaper price. The distance[] array may not properly capture these relationships between cost and stops, leading to incorrect results. 2. Let’s say you have two paths to a destination: Path A reaches the destination with 2 stops and a cost of 100. Path B reaches the same destination with 3 stops and a cost of 90. If you only use distance[], after processing Path B, the distance[] array will record 90 as the minimum cost to reach the destination, overwriting Path A's information. This could lead to an invalid solution if your algorithm later tries to use Path B (which exceeds the stop limit k).
If folks had questions of what happens in case we ended up updating the distance array for a node, in the path that is not going to make it to the destination, like in Neetcode's example, distance to C node can be 200 if K=1, but 500 if k=0. Extending the graph in that example to C to D with edge weight 100 and D to E with edge weight 100, if k is given as 1, then there might be a concern that C will be updated to 200 in the path A-B-C and it will contribute to wrong distance going forward all the way to E. But the subtle point is, because it's a longer path, the train from A -> C had already passed it and is already calculating shortest distance for nodes after C. In this case even though distance array for C is updated to 200, it doesn't affect the calculation of the train that went from A to C and further since C was only one hop away and in BFS got discovered first. So we will end up getting the correct distance at the destination node even though the final distance array doesnt match up. On the other hand, had k been greater than 3 then that A-B-C path would have been valid and distance 200 would have been valid and will contribute to the final stop at E.
we are worried only about valid number of stops not the less number of stops so if its the valid number of stops then we can push it into priority queue and increase the stops. so--> {0->3->1} stops(2) we can reach here dist=4 as less than {0-1} with dist=5 stops=1 but its valid only b'coz atmost we can make 2 stops so 0->3->1 is best option with minimum distance
for all those jinko reason nhi chamka for this: because all the incoming iterations will have >= the number of stops in the current one, and hence they will all exceed the maximum allowed limit.
@@virusdgamer8804 Your statement contradicts itself. You're right when u say ">=" but this implies that the upcoming iterations can have lesser cost with the same number of stops (there is "=" in ">=")
we should not use a priority queue that's it right. Because it always chooses the path with a minimum distance , we can't travel in other possible paths. With queue, we can travel all the paths.
priority queue might give the answer but will take a long time in pq {STOPS,{NODE,DISTANCE}} we are prioritising the less number of stops and it might be the case where the stops are greater but still the distance is less and we will take them after. size of pq will be bigger thus larger number of iterations its better to do BFS +edge relaxation with queue.
@@muditkhanna8164 yes you're' correct. PQ with stops adds unncessary log time complexity but it will work. Using standard queue with stops will also work because the priority here are stops and each time we add elements to the queue, we increase stops Both solutions work
@@muditkhanna8164 i would just use queue with no edge relaxation , we need mini distance of destination only. No of nodes in queue might be more than edge relaxed approach , But more intuitive.
at 15:20 , i have proved your point wrong by following code. /* for a same node_1:- if i take less distance to reach node_1, then it can take more stops. vice versa if it takes more distance to reach node_1, THEN IT HAS take less no of stops. this can happen in a case, where arrived at destination with less distance but stops>k, but we can arrive destination with more distance and stops distance_top + edge_weight){ dist[adj_node] = distance_top + edge_weight; pq.push({dist[adj_node], {stop+1, adj_node}}); stops[adj_node] = stop+1; }
// visiting node again but with more distance and less no of stops else if(distance_top + edge_weight > dist[adj_node] && stops[adj_node]>stop+1){ int new_adj_distance = distance_top + edge_weight; pq.push({new_adj_distance, {stop+1, adj_node}}); } } }
// i can't reach end destination with valid no of stops return -1; }
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
Summary & Logic:: It is quite straightforward that Dijakstras algo will fail because it might happen that we arrive at some node at a lesser distance but number of stops taken can be more and hence we can't move further to destination. Second questn is Why Queue logic is working here:: If we move step by step and if there is a valid answer then first time whenever we will be reaching at the destination store that distance in an answer. Now question arises what if we took more number of steps and it also reaches the destination within K stops, my answer my is it will then updated our ans. Second questn is what if we took more number of steps and it does not reaches the destination within K stops then my answer is it will just affect the intermediate node dist and as stops get exhausted it will reach not the dest and hence it will not update the final destn answer.
Those who are still getting a wrong answer on implementing the code by their own:- instead of getting distance of current node from dist vector, get it from the queue int cost = it.second.second; int cost = dist[node]; // this line will give wrong answer use above line only Don't know why this is happening, please tell if somebody has any idea about it.
Dist vector just store the minimum distance among various paths, but in queue we store the distance of our current path till that node and it still needs to be further explored, so we can not the minimum distance from dist vector for our current path which store the minimum distance from some other path.
PriorityQueue can be implemeted on this problem PriorityQueue pq=new PriorityQueue((x,y)->x.stop-y.stops); just need to compare stops in minHeap instead of distance like explained on 12:00
If you start dijkstra from end then you can do it easily.. here is the code... and yes dijkstra can be easily applied here.. class Solution { public: int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { vector adj[n]; for(int i=0; i
Another approach to solve this using Dijkistra's template(min cost PQ) is to have a 2d array instead(cost[nodes][k+1]) of the regular 1d cost array that we use in the standard Dijkstra. So instead of maintaining just the minimum cost to reach a node, we can maintain the min cost to reach a node n with i stops( 0
@takeUForward same question same src and dst from your video but increase k to 3. still it will give the path which we got for k=2 but it should give us 0-3-1-4-2 with cost of 6
@@sahiljain7871 I was thinking same and finally understood after doing a dry run, its quite difficult to understand that bit in first go, but even though dist[1] will be 4, that doesn't mean nodes 2 and 4 will have path with 3, since the queue will have other paths that will help reach to destination 2 within k stops. dist[i] array is shortest path in k stops to reach i and dist[i] does not mean dist[i+1] will be via i.
I have used distance for the priority queue and and added a greedy condition where i pushed when a node can be reached in a higher cost than the one in distance array but in less no of steps //{ Driver Code Starts #include using namespace std; // } Driver Code Ends class Solution { public: int CheapestFLight(int n, vector& flights, int src, int dst, int K) { vector edges( n ); if(src == dst) return 0; for(int i = 0 ; i < flights.size() ;i++){ edges[flights[i][0]].push_back({flights[i][1] , flights[i][2]}); } priority_queue pq; pq.push({0 , {0 , src}}); vector dist( n , {1e9 , 0}); dist[src] = {0,0}; while(!pq.empty()){ pair top = pq.top(); pq.pop(); int base = top.first; int stops = top.second.first; int city = top.second.second; for(auto it : edges[city]){ int adj = it.first; int price = it.second; if(base + price < dist[adj].first && stops > tc; while (tc--) { int n; cin>>n; int edge; cin>>edge; vector flights; for(int i=0; ix; temp.push_back(x); } flights.push_back(temp); } int src,dst,k; cin>>src>>dst>>k; Solution obj; cout
Important : Why we do consider even larger distance paths in the case of djikstra as long as it is a valid one and push it back as compared to bfs where we don't need to do so? In the bfs, it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
One another way can be use max PriorityQueue instead of min PriorityQueue. Calculate maximum price first and reduce it based on stops. However its slower.
Time complexity for Dijkstra is O(E * logV) since it is a greedy algorithm and we mark nodes as visited. Here we are visiting each node multiple times, since we are not marking them as visited, so time complexity cannot be better than Dijkstra. I think time complexity in the worst case would be (E * N) for this solution, since we can visit each 'edge' starting from each node. Please correct me if I am wrong.
logic or intuition to solve this problem:: 1) => As the given problem is to find the cheapest path from source to destination within k stops, we apply Dijkstra directly but by applying we found that if we go for a path with minimum cost/distance this may or may not be my answer 1) if the minimum distance path covers more than the given k stops to reach the destination then this path will not give an answer because this is my minimum path so the priority queue is considered only this path on this goes on further stops will increases so don't give that answer, (2)-> or if another parallel path contains less number of stops to reach the destination but the cost of this path is more than the (another path whose contains more stops but with less distance) so, priority queue will not consider this path as sorting on the basis of cost. => so avoiding the above problem:: we set the priority queue's internal sorting on the basis of stops(K) => by doing, the above modification =>, we select the path on the basis of minimum or valid (stops) => But the one thing is to notice that if we choose a simple queue instead of a priority queue then also, give me the correct answer why? => because as we can see the node reaching its neighbor stops will increase by 1 at a time so the queue will automatically store the (node, distance, stops) in a sorted fashion on the basis of stops if we remove the node from the queue we got the node with minimum stops firstly, and if the stop is greater then given stops then no further relaxation process go for other neighbors and return the distance of destination which is stored in a distance array.
Understood striver ! wonderful explanation as always, thank you very much for your efforts to make us understand !! now my feeling is graph questions are very easy 😅 Thank you so much Striver!!!
@@takeUforward Sure, can you please help me with that sheet? I have your Striver's SDE sheet but the graph questions there are not the same you are covering here. Definitely I am missing something.
Shouldn't the time complexity be O(V+E) ? Coz we're using bfs, the queue can hold V nodes and all can traverse it's adjacent nodes. Thankyou so much for your efforts Striver! I'm not sure if someone could come up with such a solution on their own when asked in an interview
At 15:20 we have to add {2,1,4 } in queue ,taking the path from 0->3->1. lets take a example where in a above example just change the cost between vertex 1->2 from 5 to 1 and then apply the same logic if we won't add it in queue this will give wrong answer
knowing about the edge case (where dijkstra's with distance as priority will fail) was the key to this question. HOW TO FIND OUT THE EDGE CASES OF PROBLEM
CODE: class Solution { public: int findCheapestPrice(int n, vector& flights, int src, int dst, int k) { vector adj(n); for(auto &v:flights)adj[v[0]].push_back({v[1],v[2]}); queue q; q.push({0,{src,0}}); vector dis(n,1e9); dis[src]=0; while(!q.empty()) { auto it=q.front(); q.pop(); int stops=it.first; int node=it.second.first; int cost=it.second.second; if(stops>k) continue; for(auto &p:adj[node]) { int adjNode=p.first; int wt=p.second; if(cost+wt
What is the advantage of using PQ? Queue should have been enough. I ran the same program with PQ as well as Queue, did not find any difference in runtime. Can u please elaborate in this particular question what advantage PQ has brought? Thanks in Advance!!
So if I set k=n-1, then problem will simplify to "finding shortest distance between src and dst". Now, using shown algorithm which uses queue as data structure will take O(E+V) time complexity to find the shortest distance, while dijkstra will take (E+V)logV, which is worse than the proposed algo. So, that means we can use above algorithm in place of dijkstra?
TC will not be 0(E) because let's say I give k=n-1 then the orginal shortes path will be solved in 0(E) times but we know org shortest path takes 0(ElogV)....it will be 0(EK) time.
At 15:32 if we have more stops to spare, we can chose the path with minimum cost even though the stops taken are more. The algorithm will fail in that case right?
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
hey bhaiya, i might be wrong but i think it has exponential tc and sc under few circumstances.
"like for edge cases"
and gfg might have weak test cases
the complexity will be O(V+E*K) and not O(V+E) if the complexity of using a queue was O(E) then why would people use dijkstras which takes a complexity of O((V+E)log(V)).
Path 0-3-1 with cost 4 and steps 2 can also be pushed in the queue....then how this solution is handling this?? pls help
@takeUforward hey!! What happens if we djikstras is followed prioritizing stops over cost?
I did the Dijsktra's same as you showed in the first step.
Just tweaked a little, I reversed the edges and then started the Dijsktra's from Destination towards source so that in case there is a path with less cost but more stops towards destination, that will be rejected midway and the path taking more cost but less stops will be considered.
Here is the code -
class Solution {
public:
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
unordered_map graph;
for(int i=0;i k) continue;
vector connectedNodes = graph[node];
for(int i=0;i newCost) {
cost[newNode] = newCost;
pq.push({newCost, newStops, newNode});
}
}
}
return -1;
}
};
This is the best question if you want to understand the inner-workings of both bfs and djikstra and the difference between them, however I feel that this question needed an in depth explanation on why we are doing the specific things that we are doing in both the queue case and the priority queue case.
@Striver at 15:20, we will consider (as per dry run and algorithm) taking the path from 0->3->1 , as the dist would be less from prev stored dist[ 1 ] and also push it in the priority queue.
I think it has to be taken because djikstra's will not only give us the the shortest path with valid number of stops to node 2 (dst) but it will also generate shortest path with valid number of stops to all the nodes in graph. So path from 0->3->1 should be the shortest path(dist = 4) which will also be covered under valid number of stops(2) rather than path 0->1 (where dist = 5, stops = 1)
Edit: valid number of stops instead of least number of stops
Same question
Yes, right there is a slight mistake in the video for this, cost of 4 should be considered instead of 5 from the time 15:15 to 15:20, while calculating this.
Hope @Striver will fix this.
@@PiyushBajaj05 Yes it was a mistake there, but we people are mature enough to understand.
yup 2+2 should be 4 instead of 5
yes.i feel .your point "Edit: valid number of stops instead of least number of stops" exactly correct
Just make sure in the if check you put the condition as (cost + edW < dist[adjNode]) and not (dist[Node] + edW < dist[adjNode]) or else edge case will fail
MISCONCEPTION: we can save some space in the queue nd do queue coz distance is already obtainable from dis[ ], so why maintain it specifically in the queue?
ANS: no coz in the queue we store the distance coming from a specific parent node ie a particular path , nd that path is used for further exploration when we take it out of the queue nd consider that paths distance ...but there can be other paths as well...dis[ ] can't maintain the paths, it just stores the path with minimum distance, which may not guarantee the path with least stops(which is our top priority)...hence we have to maintain the instance of the distance of a particular node in the queue
Well potrayed.
Well said.
this comment is worth the video explanation !!, been stuck on it for a long time. thanks for putting the light in place. Striver content quality -> 100%
Yes this is mistake commonly done
I was doing this and getting wrong ans for last test cases. Thank you for the explanation
An excellent approach to this problem. I had solved this same problem using pq and maintaining minimum cost to reach every node within each number of stops upto k, and it had worked but your solution has a way better tc and sc.
replace a condition if(curCityStop > k) continue; with below line
if(curCityStop > k) break;
because their is no need to proceed further as all further node will have stops > k
#best content in youtube #striver
Thank you
do we even need this condition as we are checking for stops
I don't understand why people find this problem confusing. Sure, it can be solved with a priority queue, but since the number of stops increases by one at each step, using a regular queue can help reduce the time complexity somehow. Another important point is that we're using the number of stops as the main criterion. If you reach a destination with a smaller distance but more stops, it's not useful. Therefore, it's better to prioritize routes with fewer stops first. Even after that, we still check routes with more stops, but only if the number of stops is within the allowed limit (≤ k). In such cases, we store those routes as well.
At 15:26 We will consider (1,3,2) with stop=1,node=3,cost=2. This is pointing to 1 with cost +2, so we will get (2,1,4) and append it to the P-Queue.
In next iteration we will pop (2,1,4) ,with stop=2,node=2cost=4,that is the minimum from heap. This pointing to node 5 with cost +5 and will give(3,2,9) and to node 4 with cost +1 and will give(3,4,5). Since we reached 2 with better cost of 9 we will update it from 10 to 9. and append both (3,2,9) and (3,4,5) to the PQ.
Now, we will pop (2,4,6) with stop=2,node=4,cost=6 (from 2nd iteration). This is pointing to node 2 with cost +1 and we will get (3,2,7).
Again we reached node 2 with lesser cost of 7 within 3 stops.
This is the most minimum we could go. As all the element left in PQ are having more stops. Hence, Striver is always right, just he missed something for which he already made us ready.
Waiting for tomorrow. 7/08/2024 for TUF+.
This is the best problem to get a grasp on dijkstra's algorithm so far!! Thanks striver for such a wonderful explanation :)
Dijkstra with PQ will also work, just don't push the value inside the queue, if value of stops > k, because we are sure that, it won't yield us the ans.
I tried with PQ but it will fail in below case if we don't put the value in the queue if value of stops > k,
[[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
src = 0 and dst = 2
k =2
The PQ will give ans = 9 but it should be 7
@@vm1662 It works correctly and answers 7.
@@vm1662 No, it will work(sharing the code)
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
//making graph
ArrayList adj=new ArrayList();
for(int i=0;i
1.Make Adj List and Distance Vector.
2.Push Src Node into queue.
3.move levelwise and increment cnt on each level.
4.when you rech dest and your count is k then break it and return distance.
I feel that the part which needs more attention is quickly skipped and some basic stuff which is quite intuitive is over stretched. Not sure whether everyone understood the correct reason to make a queue of stops, nodes and distance and not a priority queue of distance, nodes and stops
true, he should have explained more on why we do consider even larger distance paths in the case of djikstra as long as it is a valid one and push it back as compared to bfs where we don't need to do so.
In the bfs, it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
@@saumyaranjan9256 hi, confused here regarding your bfs explanation, lets take 2 paths, 3->4->1 and 3->5->6->1, suppose path 1 has 40 as distance and path 2 has 20 as distance, "it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
did you find the answer for the "reason to make a queue of stops, nodes and distance and not a priority queue of distance, nodes and stops" ?
@@kushalkollu8628Just image if you are starting from node 0 - - >3 and between 3 - - 4 there will be extra node but with small distance.
So if you take priority Queue with distance, The node 4 will never be accessed by node 1 even if it have sufficient stop.
15:30 0->3->1 is 4 and not 5 so we cant ignore that iteration
Yes
Yess..
bro, he is prioritizing steps at 1st not distance. That what he explained the mutation in normal Dijekstra .
@@rohitkumaramNo the prioritizing will be in priority queue not in the mindistance array he should include that too in the priority queue but anyway the answer will be same
yes you are right,... i was confused for a second but thought everybody can make mistakes :shrug
This was the some level good problem bhaiya which forced us to think why simply we can not use dijkstra algorithm and also normal queue can be used to solve the problem.
My intuition is on vacation !! How many have same issue?
Best Explanation I got over the web.
Thanks Striver, I had tried this question before and was trying to do a priority queue but with few added conditions as per checking distances and both stop, though that had worked but was very time consuming solution. This one is much faster and without priority queue which totally makes more sense.
While deciding to insert in priority queue, we need to sort by lowest cost and keep a check to see if cost is greater, atleast number of stops are less or not.
I see some of the comments were they are mentioning that we can omit the cost variable from the queue and take it from the distance[]. Well, that will not work. Let me tell you why:
1. Two different paths to the same node can have different numbers of stops. In some cases, a path with more stops may offer a cheaper price. The distance[] array may not properly capture these relationships between cost and stops, leading to incorrect results.
2. Let’s say you have two paths to a destination:
Path A reaches the destination with 2 stops and a cost of 100.
Path B reaches the same destination with 3 stops and a cost of 90.
If you only use distance[], after processing Path B, the distance[] array will record 90 as the minimum cost to reach the destination, overwriting Path A's information. This could lead to an invalid solution if your algorithm later tries to use Path B (which exceeds the stop limit k).
If folks had questions of what happens in case we ended up updating the distance array for a node, in the path that is not going to make it to the destination, like in Neetcode's example, distance to C node can be 200 if K=1, but 500 if k=0. Extending the graph in that example to C to D with edge weight 100 and D to E with edge weight 100, if k is given as 1, then there might be a concern that C will be updated to 200 in the path A-B-C and it will contribute to wrong distance going forward all the way to E. But the subtle point is, because it's a longer path, the train from A -> C had already passed it and is already calculating shortest distance for nodes after C. In this case even though distance array for C is updated to 200, it doesn't affect the calculation of the train that went from A to C and further since C was only one hop away and in BFS got discovered first. So we will end up getting the correct distance at the destination node even though the final distance array doesnt match up. On the other hand, had k been greater than 3 then that A-B-C path would have been valid and distance 200 would have been valid and will contribute to the final stop at E.
we are worried only about valid number of stops not the less number of stops so if its the valid number of stops then we can push it into priority queue and increase the stops. so--> {0->3->1} stops(2) we can reach here dist=4 as less than {0-1} with dist=5 stops=1 but its valid only b'coz atmost we can make 2 stops so 0->3->1 is best option with minimum distance
21:31 you can also use 'break' it will still work and obviously a bit faster
for all those jinko reason nhi chamka for this: because all the incoming iterations will have >= the number of stops in the current one, and hence they will all exceed the maximum allowed limit.
@@virusdgamer8804 Your statement contradicts itself. You're right when u say ">=" but this implies that the upcoming iterations can have lesser cost with the same number of stops (there is "=" in ">=")
The way you explain is amazing , have been solving the problems in leet code with the help of your explanation sir.
Thank You For providing Such an Amazing series on Graph !!!
Literally Its Great
we should not use a priority queue that's it right. Because it always chooses the path with a minimum distance
, we can't travel in other possible paths. With queue, we can travel all the paths.
take the pq with stops then it will choose the path with minimum stops
@@visheshagrawal8676 yes
Thank you this is really the best way of learning dijkstra limitations and work arounds!!
This is a good question to try out multiple algorithms like BFS, Dijkstra, and Bellman Ford and compare their relative time/space complexity.
For anyone stuck with Dijkstras:
Stops has priority over distance. Build the PQ based on stops
priority queue might give the answer but will take a long time in pq {STOPS,{NODE,DISTANCE}}
we are prioritising the less number of stops and it might be the case where the stops are greater but still the distance is less and we will take them after. size of pq will be bigger thus larger number of iterations
its better to do BFS +edge relaxation with queue.
@@muditkhanna8164 yes you're' correct. PQ with stops adds unncessary log time complexity but it will work.
Using standard queue with stops will also work because the priority here are stops and each time we add elements to the queue, we increase stops
Both solutions work
@@muditkhanna8164 i would just use queue with no edge relaxation , we need mini distance of destination only. No of nodes in queue might be more than edge relaxed approach , But more intuitive.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
at 15:20 , i have proved your point wrong by following code.
/*
for a same node_1:-
if i take less distance to reach node_1, then it can take more stops.
vice versa if it takes more distance to reach node_1, THEN IT HAS take less no of stops.
this can happen in a case,
where arrived at destination with less distance but stops>k,
but we can arrive destination with more distance and stops distance_top + edge_weight){
dist[adj_node] = distance_top + edge_weight;
pq.push({dist[adj_node], {stop+1, adj_node}});
stops[adj_node] = stop+1;
}
// visiting node again but with more distance and less no of stops
else if(distance_top + edge_weight > dist[adj_node] && stops[adj_node]>stop+1){
int new_adj_distance = distance_top + edge_weight;
pq.push({new_adj_distance, {stop+1, adj_node}});
}
}
}
// i can't reach end destination with valid no of stops
return -1;
}
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
return dijkstra(flights, n, src, dst, k);
}
};
*/
Summary & Logic::
It is quite straightforward that Dijakstras algo will fail because it might happen that we arrive at some node at a lesser distance but number of stops taken can be more and hence we can't move further to destination.
Second questn is Why Queue logic is working here:: If we move step by step and if there is a valid answer then first time whenever we will be reaching at the destination store that distance in an answer. Now question arises what if we took more number of steps and it also reaches the destination within K stops, my answer my is it will then updated our ans. Second questn is what if we took more number of steps and it does not reaches the destination within K stops then my answer is it will just affect the intermediate node dist and as stops get exhausted it will reach not the dest and hence it will not update the final destn answer.
Those who are still getting a wrong answer on implementing the code by their own:-
instead of getting distance of current node from dist vector, get it from the queue
int cost = it.second.second;
int cost = dist[node]; // this line will give wrong answer use above line only
Don't know why this is happening, please tell if somebody has any idea about it.
Dist vector just store the minimum distance among various paths, but in queue we store the distance of our current path till that node and it still needs to be further explored, so we can not the minimum distance from dist vector for our current path which store the minimum distance from some other path.
Thx bro❤
Because some different path with more steps but less than k will affect our answer
PriorityQueue can be implemeted on this problem
PriorityQueue pq=new PriorityQueue((x,y)->x.stop-y.stops);
just need to compare stops in minHeap instead of distance
like explained on 12:00
The way u explained ....djikstra will not work...is amazing and rare...
Solved on my own . Thanks Striver for the amazing character development in Dijkstra Algo
Why cant time complexity be O(E + V) ?
It will be E + V.
Solved this problem by own before watching the video 🤩. That feeling 🤩🤩Thanks Striver!!!
coincidence was that when I was solving this problem using Dijkstra I failed in the test case which was taken as an example by Striver Bhaiya
fantastic Brother !! You just get us feel how we should improve algorithms based on ques requirement😍
If you start dijkstra from end then you can do it easily.. here is the code... and yes dijkstra can be easily applied here..
class Solution {
public:
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
vector adj[n];
for(int i=0; i
Another approach to solve this using Dijkistra's template(min cost PQ) is to have a 2d array instead(cost[nodes][k+1]) of the regular 1d cost array that we use in the standard Dijkstra. So instead of maintaining just the minimum cost to reach a node, we can maintain the min cost to reach a node n with i stops( 0
@takeUForward same question same src and dst from your video but increase k to 3.
still it will give the path which we got for k=2 but it should give us 0-3-1-4-2 with cost of 6
Yes, I was thinking the same.
@@sahiljain7871 I was thinking same and finally understood after doing a dry run, its quite difficult to understand that bit in first go, but even though dist[1] will be 4, that doesn't mean nodes 2 and 4 will have path with 3, since the queue will have other paths that will help reach to destination 2 within k stops. dist[i] array is shortest path in k stops to reach i and dist[i] does not mean dist[i+1] will be via i.
This is the test case where i actually struggled...... thanks striver :) understood ❤
Brilliant question tbh
Thank you so much bro. you are doing wonderful job
I have used distance for the priority queue and and added a greedy condition where i pushed when a node can be reached in a higher cost than the one in distance array but in less no of steps
//{ Driver Code Starts
#include
using namespace std;
// } Driver Code Ends
class Solution {
public:
int CheapestFLight(int n, vector& flights, int src, int dst, int K) {
vector edges( n );
if(src == dst)
return 0;
for(int i = 0 ; i < flights.size() ;i++){
edges[flights[i][0]].push_back({flights[i][1] , flights[i][2]});
}
priority_queue pq;
pq.push({0 , {0 , src}});
vector dist( n , {1e9 , 0});
dist[src] = {0,0};
while(!pq.empty()){
pair top = pq.top();
pq.pop();
int base = top.first;
int stops = top.second.first;
int city = top.second.second;
for(auto it : edges[city]){
int adj = it.first;
int price = it.second;
if(base + price < dist[adj].first && stops > tc;
while (tc--) {
int n; cin>>n;
int edge; cin>>edge;
vector flights;
for(int i=0; ix;
temp.push_back(x);
}
flights.push_back(temp);
}
int src,dst,k;
cin>>src>>dst>>k;
Solution obj;
cout
Important :
Why we do consider even larger distance paths in the case of djikstra as long as it is a valid one and push it back as compared to bfs where we don't need to do so?
In the bfs, it is inherent that if we come through a path which has a larger distance than the minimum found till now for a node, then the minimum would have been found earlier by a path which had stops
One another way can be use max PriorityQueue instead of min PriorityQueue. Calculate maximum price first and reduce it based on stops. However its slower.
its a fancy bfs... great explanation!!!!!!!!!!!!!!
No need for stops k never lets value greater than k passes
Time complexity for Dijkstra is O(E * logV) since it is a greedy algorithm and we mark nodes as visited. Here we are visiting each node multiple times, since we are not marking them as visited, so time complexity cannot be better than Dijkstra. I think time complexity in the worst case would be (E * N) for this solution, since we can visit each 'edge' starting from each node. Please correct me if I am wrong.
yep, you are right. Max it can ve E*N
You can also use Priority queue but only update the distance if the new distance is minm as well as the stops is less than equal to.
Understood! So wonderful explanation as always, thank you very much!!
Thank you sir 🙏
I was trying to solve this problem on gfg and I was getting wrong answer on exactly this test case.Now I understand the mistake made by me.
did it using level order traversal and Dijkstra!
All coz of you, sir!
Thank you very much🙏
logic or intuition to solve this problem::
1) => As the given problem is to find the cheapest path from source to destination within k stops, we apply Dijkstra directly but by applying we found that if we go for a path with minimum cost/distance
this may or may not be my answer 1) if the minimum distance path covers more than the given k stops to reach the destination then this path will not give an answer because this is my minimum path so the priority queue is considered only this path on this goes on further stops will increases so don't give that answer, (2)-> or if another parallel path contains less number of stops to reach the destination but the cost of this path is more than the (another path whose contains more stops but with less distance) so, priority queue will not consider this path as sorting on the basis of cost.
=> so avoiding the above problem::
we set the priority queue's internal sorting on the basis of stops(K) =>
by doing, the above modification =>, we select the path on the basis of minimum or valid (stops)
=> But the one thing is to notice that if we choose a simple queue instead of a priority queue then
also, give me the correct answer why? => because as we can see the node reaching its neighbor stops will increase by 1 at a time so the queue will automatically store the (node, distance, stops) in a sorted fashion on the basis of stops if we remove the node from the queue we got the node with minimum stops firstly, and if the stop is greater then given stops then no further relaxation process go for other neighbors and return the distance of destination which is stored in a distance array.
Thank you so much Striver❤
Understood striver ! wonderful explanation as always, thank you very much for your efforts to make us understand !! now my feeling is graph questions are very easy 😅
Thank you so much Striver!!!
loveddd the intuition
Thank you for your explaining.
understood, thanks for the great explanation
excellent problem and explanation as well
This was an awesome explaination. Thanks!!
How many videos are you planning to make in this playlist and what all questions are you planning to cover?
You can find out all the details in the A2Z Sheet in the graphs section.
@@takeUforward Sure, can you please help me with that sheet? I have your Striver's SDE sheet but the graph questions there are not the same you are covering here. Definitely I am missing something.
@@sakshisinghal1669 there's another sheet called A2Z sheet
@@RahulKishore8 thanks got it.
if(stops>k) not required we are already checking stops
Shouldn't the time complexity be O(V+E) ? Coz we're using bfs, the queue can hold V nodes and all can traverse it's adjacent nodes. Thankyou so much for your efforts Striver! I'm not sure if someone could come up with such a solution on their own when asked in an interview
i believe we don't need a Distance array..... Simply we will do bfs on the number of stops, and keep decreasing the destination's distance.
Time complexity seems incorrect. In worst case it could go up to n^k as there could be multiple paths of almost kth length possible to any node.
Even i think that
At 15:20 we have to add {2,1,4 } in queue ,taking the path from 0->3->1. lets take a example where in a above example just change the cost between vertex 1->2 from 5 to 1 and then apply the same logic if we won't add it in queue this will give wrong answer
Thank you bhaiya
in this algo we only avoid the nodes the visited previously less edge count and weight note alter them
Needed that kind of explaination🤩🤩
jai ho prabhu !!
Thank you soooooo much bhaiya❤
Understood Sir, Thank you sir
Thank you very much. You are a genius.
knowing about the edge case (where dijkstra's with distance as priority will fail) was the key to this question.
HOW TO FIND OUT THE EDGE CASES OF PROBLEM
important at 10:55
the condition stopsk, it will continue to next, so this condition will never met.
CODE:
class Solution {
public:
int findCheapestPrice(int n, vector& flights, int src, int dst, int k) {
vector adj(n);
for(auto &v:flights)adj[v[0]].push_back({v[1],v[2]});
queue q;
q.push({0,{src,0}});
vector dis(n,1e9);
dis[src]=0;
while(!q.empty())
{
auto it=q.front();
q.pop();
int stops=it.first;
int node=it.second.first;
int cost=it.second.second;
if(stops>k) continue;
for(auto &p:adj[node])
{
int adjNode=p.first;
int wt=p.second;
if(cost+wt
Thank u striver😌😌
understood this is awesome explanations
just amazing keep uploading❣
understood striver!
striver GOD
What is the advantage of using PQ? Queue should have been enough. I ran the same program with PQ as well as Queue, did not find any difference in runtime. Can u please elaborate in this particular question what advantage PQ has brought? Thanks in Advance!!
imo the algo would be more clear if we kept track of the length of the path outside of the tuple to emphasize the level order nature
At 15:17 when node3 go to 1 it takes 4 cost not 5.
15:20 slight mistake here the distance is 4 not 5
Hi, Striver why are we checking stops k?
UNDERSTOOD
understood, thanks
thanku striver
Understood 👍
Understood sir
So if I set k=n-1, then problem will simplify to "finding shortest distance between src and dst". Now, using shown algorithm which uses queue as data structure will take O(E+V) time complexity to find the shortest distance, while dijkstra will take (E+V)logV, which is worse than the proposed algo. So, that means we can use above algorithm in place of dijkstra?
Striver Sir, Could you please elaborate the java code also.
you dont need the stops
TC will not be 0(E) because let's say I give k=n-1 then the orginal shortes path will be solved in 0(E) times but we know org shortest path takes 0(ElogV)....it will be 0(EK) time.
At 15:32 if we have more stops to spare, we can chose the path with minimum cost even though the stops taken are more. The algorithm will fail in that case right?