← DSA Atlas
Dedicated problem page · #787

Cheapest Flights Within K Stops

MediumShortest Path, Dijkstra and Minimum Spanning TreeShortest path with a hop limitBellman-Ford relaxed exactly k+1 times
Solve on LeetCode ↗
787
MediumShortest Path, Dijkstra and Minimum Spanning TreeBellman-Ford relaxed exactly k+1 timesShortest path with a hop limit

Cheapest Flights Within K Stops

There are n cities connected by some flights where flights[i] = [from, to, price]. Given src, dst, and an integer k, return the cheapest price to fly from src to dst using at most k stops (i.e. at most k+1 flights). If there is no such route, return -1.

Open official problem prompt ↗
In plain English

Find the cheapest airfare from src to dst that uses no more than k intermediate stops.

Picture it like this

Like booking a trip on a budget where each layover uses up an allowance: you want the cheapest ticket but you can only tolerate up to k connections.

Example
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
Why
0->1->3 costs 100+600=700 using 1 stop; the cheaper 0->1->2->3 (400) needs 2 stops, exceeding k.
Constraints
1 <= n <= 1000 <= flights.length <= n*(n-1)/2flights[i] = [from_i, to_i, price_i]0 <= from_i, to_i < nfrom_i != to_i1 <= price_i <= 10^40 <= src, dst, k < nsrc != dst
Pattern lesson

See the pattern, then code

Shortest path with a hop limit
Recognition clue

A shortest/cheapest path constrained by a maximum number of edges is the signature of layer-limited Bellman-Ford.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Relaxing all edges once lets paths grow by one flight. Doing it k+1 times finds the cheapest cost reachable with at most k+1 flights, i.e. k stops. Using a snapshot per round prevents a single round from chaining several flights.

New words, made simpleKnow these before the algorithm
Stop
An intermediate city; k stops means at most k+1 flights.
Relaxation round
One pass over all edges, extending every path by at most one flight.
Snapshot (tmp)
A frozen copy of distances used so a round cannot chain multiple flights.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Plain Dijkstra by cost

Can wrongly settle a city via a cheap-but-too-many-stops route, missing valid costlier answers.

Expand cheapest cost first, ignoring stop count.

Time O(E log V)Space O(V)
Best choiceBellman-Ford with k+1 rounds

Directly bounds the number of edges, so it respects the stop limit exactly.

Relax all edges k+1 times using a per-round snapshot.

Time O(k * E)Space O(n)
The rule we keep true

Invariant

After round i, dist[v] is the cheapest cost to reach v using at most i flights.

Why this is correct

Reasoning

Each round extends paths by exactly one edge because relaxations read the previous round's snapshot; after k+1 rounds dist[dst] is the cheapest cost using at most k+1 flights, which is exactly k stops.

The algorithm in three movesSay these aloud before coding
1Initialize dist[src]=0 and all others to infinity

round0 dist=[0,inf,inf,inf]

2Repeat k+1 times: copy dist into tmp, then relax every edge into tmp

round1 tmp=[0,100,inf,inf]

3Assign tmp back to dist after each full round

round2 tmp=[0,100,200,700] -> dist[3]=700

4Return dist[dst] or -1 if still infinite

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
33
1 · Readsrc=0
2 · AskStarting costs?
3 · Update statedist=[0,inf,inf,inf]
4 · ResultOnly src is 0
Key takeaway

Cities 0..3; cheapest route within 1 stop is 0->1->3 = 700.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Initialize distances

    Source starts at 0, everything else infinite.

  2. 2
    Lines 6-7k+1 rounds with a snapshot

    Copy dist so relaxations in this round only see last round's values.

  3. 3
    Lines 8-10Relax every edge

    Improve tmp[v] using the frozen dist[u], adding one flight.

  4. 4
    Lines 11Commit the round

    Swap tmp back so the next round builds on it.

  5. 5
    Lines 12Return

    Cheapest bounded cost, or -1 if dst stayed infinite.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k == 0 -> only direct flights allowed
  • No path within k stops -> -1
  • A cheaper path exists but uses too many stops (must be rejected)
  • Disconnected dst
!

Common beginner mistakes

  • Relaxing in place without the snapshot lets one round chain multiple flights, over-counting allowed stops
  • Off-by-one: k stops means k+1 edges, so loop k+1 times
  • Using Dijkstra keyed only on cost can prune a valid answer that costs more but uses fewer stops
Check your understanding

Why copy dist into tmp each round instead of relaxing in place?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#815Bus RoutesUnweighted shortest path (fewest transfers)#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)