Solve \u201cCheapest Flights Within K Stops\u201d (LeetCode 787) in plain Python using a BFS queue and a cost array. Learn the intuition, code, and dry-run for cheapest flights first-time success.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n You have<\/em> Return the cheapest possible price<\/strong>. Cities are nodes; flights are directed edges<\/strong> with weights = prices.<\/p>\n\n\n\n Dijkstra does not limit the number of edges<\/strong>; it might return a cheaper path that uses too many stops. This idea is similar to Bellman-Ford limited to 1. What does the problem ask?<\/h2>\n\n\n\n
n<\/code><\/strong> cities numbered 0 \u2026 n-1<\/code> and a list of flights[from, to, price]<\/code>.
You must fly from src<\/code><\/strong> to dst<\/code><\/strong> but may take at most k<\/code> intermediate stops<\/strong>
(so at most k + 1<\/code> flights in total).<\/p>\n\n\n\n
If no such route exists, return -1<\/code><\/strong>.<\/p>\n\n\n\n
\n\n\n\n2. Quick examples<\/h2>\n\n\n\n
n<\/code><\/th>flights<\/code><\/th>src<\/code> \u2192 dst<\/code>, k<\/code><\/th>Answer<\/th> Why<\/th><\/tr><\/thead> 3<\/td> [[0,1,100],[1,2,100],[0,2,500]]<\/code><\/td>0\u21922<\/code>, k=1<\/code><\/td>200<\/code><\/td>0\u21921\u21922 costs 200 (1 stop).<\/td><\/tr> 3<\/td> same flights<\/td> 0\u21922<\/code>, k=0<\/code><\/td>500<\/code><\/td>Only direct flight allowed.<\/td><\/tr> 4<\/td> [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]<\/code><\/td>0\u21923<\/code>, k=1<\/code><\/td>500<\/code><\/td>Cheapest path needs 2 stops, which exceeds k<\/code>.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n3. Intuition & approach<\/h2>\n\n\n\n
3.1 Graph view<\/h3>\n\n\n\n
3.2 Why not plain Dijkstra?<\/h3>\n\n\n\n
We need a structure that also keeps track of how many flights<\/strong> we have taken so far.<\/p>\n\n\n\n3.3 BFS with cost pruning<\/h3>\n\n\n\n
\n
A standard BFS queue processes nodes layer by layer; here each layer means \u201cone more flight taken\u201d.<\/li>\n\n\n\n(stopsUsed, city, costSoFar)<\/code>
We never push a state whose stopsUsed<\/code> already exceeded k + 1<\/code> flights.<\/li>\n\n\n\nmin_cost[city]<\/code> array<\/strong>
Stores the cheapest price found so far for that city with any number of stops \u2264 k + 1<\/strong>.
We only push a new state if we have really improved that city\u2019s cost.<\/li>\n\n\n\n
We may still keep exploring even after seeing dst<\/code> once, because another path with the same or fewer stops could be cheaper\u2014but the min_cost<\/code> check prevents endless work.<\/li>\n<\/ol>\n\n\n\nk + 1<\/code> rounds<\/strong>, but implemented with a queue for clarity.<\/p>\n\n\n\n
\n\n\n\n4 Code<\/h2>\n\n\n\n