AlgoInsight

DSA problem

Cheapest Flights Within K Stops

MediumShortest PathPattern: Shortest Pathtop75FreeAmazonGoogleMicrosoftUberBloomberg

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. You are also given three integers src, dst, and k: return the cheapest price from src to dst with at most k stops, or -1 if no such route exists.

Note that "at most k stops" means the path uses at most k + 1 edges (a direct flight counts as zero stops and one edge). This stop-count constraint is what makes the problem harder than a plain Dijkstra: a path with more edges can sometimes be cheaper, so pruning solely by minimum cost can miss the answer.

The Bellman-Ford perspective fits the constraint naturally. Relax all edges k + 1 times, but read from a snapshot of the distance array taken at the start of each round so that each round adds at most one edge to every path. After k + 1 rounds, the minimum cost to reach any node using at most k + 1 edges is fully computed.

An alternative is a modified Dijkstra carrying the triple (cost, node, stops_used) in the heap. The catch is that you cannot mark a node as final on first pop, because a later pop with more stops could allow more edges to relax onward. Instead, prune by tracking the minimum stops seen at each node so far, skipping any state that uses more stops without being cheaper. Both approaches solve the problem in polynomial time; Bellman-Ford is conceptually simpler when the stop limit is small.

Examples

Example 1
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: With at most 1 stop, the cheapest route is 0 -> 1 -> 3 costing 100 + 600 = 700. The path 0 -> 1 -> 2 -> 3 has 2 stops, which violates the constraint even though it costs 400.
Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: With at most 1 stop, 0 -> 1 -> 2 costs 200 and is cheaper than the direct flight 0 -> 2 costing 500.
Example 3
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With 0 stops only direct flights are allowed, so the answer is the direct 0 -> 2 flight costing 500.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

shortest-pathbellman-forddynamic-programminggraph

Browse all DSA problems