G-38. Cheapest Flights Within K Stops

GfG-Problem Link: bit.ly/3UIneer
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

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

[@ThisisCuriousclue]

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

[@vaibhavpratapsingh9956]

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)).

[@harshitagrahari9241]

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

[@tooovisibletosee]

@takeUforward hey!! What happens if we djikstras is followed prioritizing stops over cost?

[@pranshu_awasthi]

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; } };

[@anonymouse3488]

@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

[@vikrambabariya5166]

Same question

[@PiyushBajaj05]

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.

[@amanbhadani8840]

@@PiyushBajaj05 Yes it was a mistake there, but we people are mature enough to understand.

[@abhimanyuraizada7713]

yup 2+2 should be 4 instead of 5

[@SaiKumarSays]

yes.i feel .your point "Edit: valid number of stops instead of least number of stops" exactly correct

[@saumyaranjan9256]

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.

[@ashfaqmurshed503]

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

[@takeUforward]

Well potrayed.

[@Yash6189]

Well said.

[@balajiarumugam1876]

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%

[@gauravkungwani]

Yes this is mistake commonly done

[@sunkuthanmai729]

I was doing this and getting wrong ans for last test cases. Thank you for the explanation

[@kanishq8684]

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.

[@no_num_no_gum]

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

[@saumyaranjan9256]

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

[@Aks-47]

@@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

[@kushalkollu8628]

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" ?

[@Kai-cz7wf]

​@@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.

[@pulkitchausali1354]

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

[@priyanshkumar17]

Thank you

[@AMANZAKIRHUSAINMODAN]

My intuition is on vacation !! How many have same issue?

[@usmanganimakandar9293]

15:30 0->3->1 is 4 and not 5 so we cant ignore that iteration

[@I_U_I_T_C]

Yes

[@AJ-xc3ks]

Yess..

[@rohitkumaram]

bro, he is prioritizing steps at 1st not distance. That what he explained the mutation in normal Dijekstra .

[@akhilbaratam2560]

@@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

[@Pranauv]

yes you are right,... i was confused for a second but thought everybody can make mistakes :shrug

[@pavansrinivas4388]

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

[@rishavkumar2182]

This is the best problem to get a grasp on dijkstra's algorithm so far!! Thanks striver for such a wonderful explanation :)

[@AkashSharma-ij4sn]

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

[@Dontpushyour_luck]

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.

[@riddhiroy1428]

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.

[@aryanmalguri3275]

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.

[@vm1662]

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

[@krishpatel6741]

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.

[@ashishkumaryadav5252]

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.

[@amanbhadani8840]

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.

[@amanbhadani8840]

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.

[@dolbyagarwal9316]

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.

[@AjaySingh-xy9zq]

Thank You For providing Such an Amazing series on Graph !!! Literally Its Great

[@skt7088]

Why cant time complexity be O(E + V) ?

[@YeaOhYeahh]

It will be E + V.

[@sakinobashi168]

21:31 you can also use 'break' it will still work and obviously a bit faster

[@virusdgamer8804]

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.

[@gaganagarwal7218]

@@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 ">=")

[@ameypate9610]

This is a good question to try out multiple algorithms like BFS, Dijkstra, and Bellman Ford and compare their relative time/space complexity.

[@vikustorm3411]

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); } }; */

[@kartikdalai7998]

@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]

Yes, I was thinking the same.

[@skblabla]

@@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.

[@yoMisterWhyte]

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.

[@kasamadhu3509]

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.

[@visheshagrawal8676]

take the pq with stops then it will choose the path with minimum stops

[@priyanshkumar17]

@@visheshagrawal8676 yes

[@stith_pragya]

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

[@divyatejaswinivengada6368]

Thank you this is really the best way of learning dijkstra limitations and work arounds!!

[@mohmedfaizrozdarsyed1234]

The way you explain is amazing , have been solving the problems in leet code with the help of your explanation sir.

[@rudrakhare1158]

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+.

[@beinghappy9223]

Solved on my own . Thanks Striver for the amazing character development in Dijkstra Algo

[@Moch117]

For anyone stuck with Dijkstras: Stops has priority over distance. Build the PQ based on stops

[@muditkhanna8164]

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.

[@Moch117]

@@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

[@iamnoob7593]

@@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.

[@sameerbhardwaj8949]

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.

[@mohammadkaif8143]

yep, you are right. Max it can ve E*N

[@mohammadkaif8143]

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.

[@kaichang8186]

understood, thanks for the great explanation

[@ironeagle1709]

Solved this problem by own before watching the video 🤩. That feeling 🤩🤩Thanks Striver!!!

[@secretvibz6300]

fantastic Brother !! You just get us feel how we should improve algorithms based on ques requirement😍

[@AmitkumarSaw-uc5bu]

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

[@nba_nerd]

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.

[@ADNANAHMED-eo5xx]

Even i think that

[@nikee-ux5kl]

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

[@rushidesai2836]

Brilliant question tbh

[@gyanaranjansahoo6258]

This is the test case where i actually struggled...... thanks striver :) understood ❤

[@prasannasippa5962]

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!!!

[@mohammadkaif8143]

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.

[@cinime]

Understood! So wonderful explanation as always, thank you very much!!

[@lavanyam3224]

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

[@saumyaranjan9256]

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

[@AngadSharma]

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

[@KS0607]

The way u explained ....djikstra will not work...is amazing and rare...

[@jaishriharivishnu]

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.

[@priytoshtripathi8000]

This was an awesome explaination. Thanks!!

[@user-ie8sy7wo4m]

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.

[@vishakhajadhav7064]

Thank you so much Striver❤

[@ishangujarathi10]

loveddd the intuition

[@UECAshutoshKumar]

Thank you sir 🙏

[@sakshisinghal1669]

How many videos are you planning to make in this playlist and what all questions are you planning to cover?

[@takeUforward]

You can find out all the details in the A2Z Sheet in the graphs section.

[@sakshisinghal1669]

@@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.

[@RahulKishore8]

@@sakshisinghal1669 there's another sheet called A2Z sheet

[@sakshisinghal1669]

@@RahulKishore8 thanks got it.

[@shadanhussain5107]

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

[@iltabishkhan]

At 15:17 when node3 go to 1 it takes 4 cost not 5.

[@abhisheksingh-np8yi]

No need for stops k never lets value greater than k passes

[@VimanshMahajan]

if(stops>k) not required we are already checking stops

[@lokeshroy3944]

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

[@josephstark5810]

in this algo we only avoid the nodes the visited previously less edge count and weight note alter them

[@hardikgupta7946]

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.

[@phuonganho9302]

Thank you for your explaining.

[@ankitraheja9524]

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!!

[@rajneeshdubey5779]

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

[@akshatsharma5426]

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.

[@Ramu9119]

excellent problem and explanation as well

[@RohithChandra.Kae21b054]

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?

[@luckygamers8068]

Needed that kind of explaination🤩🤩

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@solitucedagar4298]

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.

[@raghavmanish24]

thanku striver

[@shaurydeep]

the condition stopsk, it will continue to next, so this condition will never met.

[@nagame859]

did it using level order traversal and Dijkstra! All coz of you, sir! Thank you very much🙏

[@averylazyandweirdhuman]

Hi, Striver why are we checking stops k?

[@reggiehurley1479]

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

[@nithishkumar8658]

i am not clear about y cant we stop when we reach the destination can anyone help me!!

[@varunaggarwal7126]

19:05

[@joshrak3412]

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

[@adarshrajshrivastava1113]

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?

[@badaljha6257]

Thank u striver😌😌

[@omkarkadam309]

isn't this just like a BFS of level-wise traversal, along with array tracking distance ??

[@Nothing-eg9ol]

just amazing keep uploading❣

[@technologybaba192]

Understood

[@1tav0]

understood this is awesome explanations

[@rishabhagarwal8049]

Understood Sir, Thank you sir

[@ronitkaushik4634]

important at 10:55

[@keertilata20]

15:20 slight mistake here the distance is 4 not 5

[@samranayesrab5546]

Is it necessary to have an extra check of stops K then continue(line 27)?

[@kalyankumar1372]

@samrana, I too find it unnecessary

[@amanasrani6405]

Thank you soooooo much bhaiya❤

[@Tech.IT.e]

Striver Sir, Could you please elaborate the java code also.

[@YashGaneriwal-je6rh]

understood

[@rbk.technology4747]

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.

[@vaibhavagrawal3381]

I have the same doubt.

[@vaibhavagrawal3381]

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.

[@abhirupbasu3386]

it should O(V+E).think just like normal bfs.

[@user-le6ts6ci7h]

​@@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

[@cscoded]

@@abhirupbasu3386 no man in normal bfs we maintain visited array and visit once ,, here the time complexity should be o(ek)

[@hrushi_borhade]

understood striver!

[@LokeshSharma-hm5jz]

understood, thanks

[@amansinghal4663]

I didn't get the time complexity part ..... It should be O(E+V) .....same as the complexity of BFS in directed graphs.

[@devruhela4944]

jai ho prabhu !!

[@charan775]

I don't understand why we don't use {Steps, {Dist, Node}}

[@Learnprogramming-q7f]

Thank you bhaiya

[@gypsygirlkigypsylife]

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;