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.
So as per my understanding the only difference between this algo and basic dijkstra's is that instead of distance we give priority to nodes in the queue, correct? In other words, difference in just the way we store the tuple in queue. Or am I missing something?
@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.
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.
@@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
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 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.
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%
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.
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+.
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 ">=")
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 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.
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
@@vm1662 Just sort the priority queue one the basis of stops instead of price, It will work fine. PriorityQueue q = new PriorityQueue((x,y) -> x.s - y.s); class Pair { int n, p, s; Pair(int n, int p, int s) { this.n = n; this.p = p; this.s = s; } } here n is vertex, p is price till that vertex and s is stops till that vertex.
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.
yes this is how I solved it as well. Seems easier to modify bfs to skip paths with a lower value from same or lower level, than to modify Dijkstra to make it not greedy and storing triplet variables to keep track of the level.
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.
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
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) {
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.
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.
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
yes, striver did a mistake and according to the code he wrote also, {2, 1, 4} will go into the queue. But still it won't affect the right answer which is 7, why, because {2, 1, 4} will stay in the queue along with {1,1,5}, notice we aren't removing it when a shorter distance path came. So both will stay in the queue and at the end due to both of them {3, 2, 9} and {3, 2, 7} and {2,2,10} will be in the queue and we dont just stop, so eventually the minimum will get considered which is 7. So the point is, yes by strivers code only, {2, 1, 4} will go into the queue but it wont get considered in final, its just trying all the possibilities. Notice that in this crooked Dijkstra logic, the priority queue is non existent, so its not even a greedy algorithm, its simply trying all possibilities right by normal bfs. Hope it helps.
@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 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).
well well what if we put a condition to insert in heap with the condition to insert when stops < k wont this work? edit -> it wont work because reaching a destination 'k' could take 0 stops with greater distance than taking 1 stops with lesser distance it would consume our 1 stop hence traversing every possibility is required in this question
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?
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.
In this problem, please note that the same edge can be traversed multiple times. It's because we can arrive at a node once again with higher number of stops but lesser cost and hence it can be pushed into the queue once again. When removing such elements from the queue all the adjacent neighbours will also be traversed again. Hence the worst case time complexity has to be O(V + E*K), each edge can be traversed at most K times.
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.
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
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
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.
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
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?
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!!!
Why do we store stops as the first priority and not price? What if we store price as the first priority but before inserting neighbors into the priority queue we just check if the number of stops > k and if it is then dont insert into PQ itself? What is the error in this approach
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.
Why is (2,4,6) getting executed before (2,2,10) in the priority queue at 15:47 , can anyone give valid explanation Edit: basically later in the video he told to use queue which resolves the issue, so yeah it won't work with pq but will work with queue
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!!
should it not be if node==destination then continue,as we are considering for stop+1 also ,while it not skip the stop+1=3 (in example) with the statement if (stop>k) continue;
@@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.
Striver one doubt please reply and clarify. Time complexity should be O(EV) right Bcoz see the outer while loop can run at Max for E. Then comes inner for loop iteration of adj nodes. A node at Max can have V-1 neighbours. So totally it boils to O(EV) right? If not please give me counter example and clarification over it. This judgement of time complexity is bit tougher for me.
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.
So as per my understanding the only difference between this algo and basic dijkstra's is that instead of distance we give priority to nodes in the queue, correct? In other words, difference in just the way we store the tuple in queue. Or am I missing something?
@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
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.
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
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
This is the best problem to get a grasp on dijkstra's algorithm so far!! Thanks striver for such a wonderful explanation :)
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.
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
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.
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+.
Glad that I found the optimal approach without watching video , Thanks Striver bhai
My intuition is on vacation !! How many have same issue?
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 ">=")
Best Explanation I got over the web.
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.
Thank You For providing Such an Amazing series on Graph !!!
Literally Its Great
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.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
The way you explain is amazing , have been solving the problems in leet code with the help of your explanation sir.
Why cant time complexity be O(E + V) ?
It will be E + V.
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
@@vm1662
Just sort the priority queue one the basis of stops instead of price, It will work fine.
PriorityQueue q = new PriorityQueue((x,y) -> x.s - y.s);
class Pair {
int n, p, s;
Pair(int n, int p, int s) {
this.n = n;
this.p = p;
this.s = s;
}
}
here n is vertex, p is price till that vertex and s is stops till that vertex.
@@vm1662 same man
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.
yes this is how I solved it as well. Seems easier to modify bfs to skip paths with a lower value from same or lower level, than to modify Dijkstra to make it not greedy and storing triplet variables to keep track of the level.
Thank you this is really the best way of learning dijkstra limitations and work arounds!!
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.
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😍
This is the test case where i actually struggled...... thanks striver :) understood ❤
Hi, Striver why are we checking stops k?
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
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.
Solved on my own . Thanks Striver for the amazing character development in Dijkstra Algo
This is a good question to try out multiple algorithms like BFS, Dijkstra, and Bellman Ford and compare their relative time/space complexity.
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);
}
};
*/
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
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
Really Really Good Question!. Striver OP!!!
In line no 27, it's better to use 'break' instead of continue.
Thank you so much bro. you are doing wonderful job
The way u explained ....djikstra will not work...is amazing and rare...
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
loveddd the intuition
Thank you so much Striver❤
yes, striver did a mistake and according to the code he wrote also, {2, 1, 4} will go into the queue. But still it won't affect the right answer which is 7, why, because {2, 1, 4} will stay in the queue along with {1,1,5}, notice we aren't removing it when a shorter distance path came. So both will stay in the queue and at the end due to both of them {3, 2, 9} and {3, 2, 7} and {2,2,10} will be in the queue and we dont just stop, so eventually the minimum will get considered which is 7. So the point is, yes by strivers code only, {2, 1, 4} will go into the queue but it wont get considered in final, its just trying all the possibilities. Notice that in this crooked Dijkstra logic, the priority queue is non existent, so its not even a greedy algorithm, its simply trying all possibilities right by normal bfs. Hope it helps.
its a fancy bfs... great explanation!!!!!!!!!!!!!!
Solved this problem by own before watching the video 🤩. That feeling 🤩🤩Thanks Striver!!!
Understood! So wonderful explanation as always, thank you very much!!
This was an awesome explaination. Thanks!!
@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.
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).
understood, thanks for the great explanation
well well what if we put a condition to insert in heap with the condition to insert when
stops < k
wont this work?
edit -> it wont work because reaching a destination 'k' could take 0 stops with greater distance than taking 1 stops with lesser distance
it would consume our 1 stop
hence traversing every possibility is required in this question
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.
Thank you for your explaining.
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?
excellent problem and explanation as well
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.
Needed that kind of explaination🤩🤩
At 15:17 when node3 go to 1 it takes 4 cost not 5.
Brilliant question tbh
Simply awesome!!!
Thank you sir 🙏
In this problem, please note that the same edge can be traversed multiple times. It's because we can arrive at a node once again with higher number of stops but lesser cost and hence it can be pushed into the queue once again. When removing such elements from the queue all the adjacent neighbours will also be traversed again. Hence the worst case time complexity has to be O(V + E*K), each edge can be traversed at most K times.
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.
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
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
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.
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
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?
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!!!
Why do we store stops as the first priority and not price? What if we store price as the first priority but before inserting neighbors into the priority queue we just check if the number of stops > k and if it is then dont insert into PQ itself? What is the error in this approach
if(stops>k) not required we are already checking stops
i am not clear about y cant we stop when we reach the destination can anyone help me!!
19:05
just amazing keep uploading❣
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
Thank u striver😌😌
No need for stops k never lets value greater than k passes
I don't get it if we skip the 0->3->1 path, if the destination had been 4, then the answer that is getting stored for 4 is incorrect.
Thank you very much. You are a genius.
Thank you soooooo much bhaiya❤
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.
in this algo we only avoid the nodes the visited previously less edge count and weight note alter them
Is it necessary to have an extra check of stops K then continue(line 27)?
@samrana, I too find it unnecessary
Why is (2,4,6) getting executed before (2,2,10) in the priority queue at 15:47 , can anyone give valid explanation
Edit: basically later in the video he told to use queue which resolves the issue, so yeah it won't work with pq but will work with queue
understood this is awesome explanations
why do we write continue statement over there ?
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!!
isn't this just like a BFS of level-wise traversal, along with array tracking distance ??
Understood Sir, Thank you sir
should it not be if node==destination then continue,as we are considering for stop+1 also ,while it not skip the stop+1=3 (in example) with the statement if (stop>k) continue;
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.
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.
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
understood striver!
Striver Sir, Could you please elaborate the java code also.
Why haven't we consider maintaing a visited array ?
15:20 slight mistake here the distance is 4 not 5
Striver one doubt please reply and clarify.
Time complexity should be O(EV) right
Bcoz see the outer while loop can run at Max for E.
Then comes inner for loop iteration of adj nodes. A node at Max can have V-1 neighbours.
So totally it boils to O(EV) right?
If not please give me counter example and clarification over it.
This judgement of time complexity is bit tougher for me.
I have the same doubt.
vector < int > cost(n,1e9);
cost[src] = 0;
for(int i=0;i cost2 = cost;
for(auto x: flights){
if(cost2[x[1]] > cost[x[0]] + x[2]) cost2[x[1]] = cost[x[0]] + x[2];
}
cost = cost2;
}
return cost[dst] == 1e9 ? -1 : cost[dst];
This can be simple solution with same complexity.
it should O(V+E).think just like normal bfs.
@@abhirupbasu3386 it is not like normal bfs , in normal bfs u are vsiiting each node and edgr as ingle time , so the time complexity bis v+e
@@abhirupbasu3386 no man in normal bfs we maintain visited array and visit once ,, here the time complexity should be o(ek)
Can someone tell me why the number of stops has to be given priority and not the shortest distance? couldn't understand.
why to use continue in line 27?