Problem Statement

Cheapest Flights Within K Stops

You have n cities. Some cities are connected by flights, and each flight has a price. You want the cheapest total price to get from a start city (src) to an end city (dst). The catch: you are only allowed at most k stops along the way. A "stop" is a city you land in between the start and the end. So if k is 1, you can take a flight, land once in the middle, then take one more flight. That means at most k+1 flights total. The tool we use here is called Bellman-Ford. Think of it like buying flights one round at a time. In round one you only look at flights that leave directly from your start. In round two you look at flights that build on top of what you found in round one, so now you have used two flights. Each round adds the chance to take one more flight. We do k+1 rounds because k stops means up to k+1 flights. The key trick is that within a single round we are not allowed to chain two new flights together, so we work off a frozen copy of the prices from the round before. That copy is what keeps us honest about the stop limit.

mediumGraphDynamic ProgrammingGraphsTime: O(K * E) · Space: O(V)

Signals to notice

cheapest flight with at most k stopsshortest path with hop constraintmodified BFS/Bellman-Ford

Brute force first

Try all paths with ≤ k+1 edges — exponential. Enumerates every possible route. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Bellman-Ford with k+1 relaxation rounds. Or BFS with (cost, node, stops) states and a min-heap (modified Dijkstra). Each round relaxes all edges, but only for k+1 rounds. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src=0, dst=3, k=1`

init: prices=[0, inf, inf, inf] (only src=0 reachable, cost 0)
round i=0, temp=copy: relax [0,1,100] -> temp[1]=100; others need prices[u]=inf, skipped -> prices=[0, 100, inf, inf] (paths with <=1 edge)
round i=1, temp=copy=[0,100,inf,inf]: [0,1,100] keeps temp[1]=100
  [1,2,100] -> temp[2]=min(inf,100+100)=200; [1,3,600] -> temp[3]=min(inf,100+600)=700
  [2,0,100] & [2,3,200] skipped (prices[2]=inf this round) -> prices=[0, 100, 200, 700] (paths with <=2 edges = at most 1 stop)
loop ends (k+1=2 rounds done); prices[dst=3]=700 != inf
return 700

What must stay true

After i rounds of Bellman-Ford, the shortest paths using at most i edges are computed. Running k+1 rounds gives the answer with the stop constraint. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

prices = [inf] * n; prices[src] = 0
repeat k+1 times:
    temp = copy(prices)          # snapshot so each round adds at most 1 hop
    for (u, v, w) in flights:
        if prices[u] != inf:
            temp[v] = min(temp[v], prices[u] + w)
    prices = temp
return prices[dst] if prices[dst] != inf else -1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using standard Dijkstra without the stop constraint — Dijkstra finds the cheapest path regardless of stops. You need to track stops as part of the state. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Graphs Pattern