Cheapest Flights Within K Stops sounds like a textbook Dijkstra problem. You have nodes, edges with weights, and you want minimum cost. Standard graph shortest-path. Dijkstra is your hammer. So you reach for it — and it gives you the wrong answer.
The problem adds one dimension Dijkstra cannot handle: a constraint on the number of stops. With k=1, you can only make 1 intermediate stop — a maximum of 2 flight legs. Dijkstra finds the cheapest path regardless of how many hops it takes. When the cheapest path uses 2 stops and k=1, Dijkstra returns a path you are not allowed to take.
(cost=3). But that path uses 2 stops (1 and 2). With k=1, only 1 stop allowed — this path is INVALID.Dijkstra's greedy invariant is: once a node is settled (its minimum cost finalized), it is never revisited. This invariant assumes that reaching a node with lower cost is always better. But here “better” depends on two dimensions simultaneously: cost AND number of hops taken. A cheaper path that uses more hops than k allows is useless. Dijkstra has no way to prefer “slightly more expensive but fewer hops” over “cheapest but over the hop limit.”
You can hack Dijkstra with a state tuple (node, hops_used) as the queue key — but that changes the algorithm's complexity and structure significantly. There is a cleaner approach: think of the problem not as “navigate a graph” but as “relax all edges in waves, one wave per allowed hop.”
With k=1 (at most 1 stop), which path is actually valid and what is its cost?