Module 21 · Union-Find, Weighted Graphs, and Minimum Spanning Trees

209. Cheapest Flight Within K Stops

Interview · Download this solution · All solutions and shared helpers

Problem

Return the cheapest price from source to destination using at most k intermediate stops in a directed flight graph. n vertices use zero-based labels; flights are (u,v,nonnegative_price), and k>=0. At most k+1 flight edges are allowed. Return -1 if impossible; source==destination costs zero.

Examples

Example 1

cheapest_flight(3,[(0,1,1),(1,2,1),(0,2,10)],0,2,0)
=> 10

No intermediate stop permits only the direct flight.

Example 2

cheapest_flight(3,[(0,1,1),(1,2,1),(0,2,10)],0,2,1)
=> 2

One intermediate stop permits the cheaper two-edge route.

Example 3

cheapest_flight(2,[],0,1,3)
=> -1

No budget can create a missing route.

Reveal the worked solution and reasoning

Why this mechanism works

The edge budget is part of the state. A cheap route with too many edges cannot replace a more expensive route with budget remaining. Use repeated relaxation layers: layer j stores the best cost using at most j edges. Read only the previous layer and write a fresh copy to prevent one pass from consuming several flights.

State and boundaries

dist holds costs using at most the completed number of edges. next_dist begins as a copy, retaining routes that use fewer edges.

Protocol

Initialize source cost zero.
Repeat k+1 layers.
Copy the previous costs.
Relax every flight using only old dist values.
Replace dist after the full edge scan.
Return destination cost or -1.

Visualization

0->1 cost 1, 1->2 cost 1, 0->2 cost 10
k=0 permits one edge -> 10
k=1 permits two edges -> 2
fresh layers enforce the difference

Python implementation

def cheapest_flight(n, flights, source, destination, k):
    dist = [float('inf')] * n
    dist[source] = 0
    for _ in range(k + 1):
        next_dist = dist.copy()
        for u, v, price in flights:
            next_dist[v] = min(next_dist[v], dist[u] + price)
        dist = next_dist
    return -1 if dist[destination] == float('inf') else dist[destination]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

cheapest_flight(3,[(0,1,1),(1,2,1),(0,2,10)],0,2,0)

L2 cheapest_flight: dist = [float('inf')] * n
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[inf, inf, inf]

L3 cheapest_flight: dist[source] = 0
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]

L4 cheapest_flight: for _ in range(k + 1):
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0

L5 cheapest_flight: next_dist = dist.copy()
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, inf, inf]

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, inf, inf]; u=0; v=1; price=1

L7 cheapest_flight: next_dist[v] = min(next_dist[v], dist[u] + price)
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=0; v=1; price=1

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=1; v=2; price=1

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=0; v=2; price=10

L7 cheapest_flight: next_dist[v] = min(next_dist[v], dist[u] + price)
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, inf, inf]; _=0; next_dist=[0, 1, 10]; u=0; v=2; price=10

L8 cheapest_flight: dist = next_dist
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=0; dist=[0, 1, 10]; _=0; next_dist=[0, 1, 10]; u=0; v=2; price=10

Result: 10. No intermediate stop permits only the direct flight.

cheapest_flight(3,[(0,1,1),(1,2,1),(0,2,10)],0,2,1)

L2 cheapest_flight: dist = [float('inf')] * n
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[inf, inf, inf]

L3 cheapest_flight: dist[source] = 0
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]

L4 cheapest_flight: for _ in range(k + 1):
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0

L5 cheapest_flight: next_dist = dist.copy()
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0; next_dist=[0, inf, inf]

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0; next_dist=[0, inf, inf]; u=0; v=1; price=1

L7 cheapest_flight: next_dist[v] = min(next_dist[v], dist[u] + price)
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=0; v=1; price=1

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=1; v=2; price=1

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, inf, inf]; _=0; next_dist=[0, 1, inf]; u=0; v=2; price=10

... 4 intermediate state changes omitted ...

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, 1, 10]; _=1; next_dist=[0, 1, 10]; u=1; v=2; price=1

L7 cheapest_flight: next_dist[v] = min(next_dist[v], dist[u] + price)
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, 1, 10]; _=1; next_dist=[0, 1, 2]; u=1; v=2; price=1

L6 cheapest_flight: for u, v, price in flights:
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, 1, 10]; _=1; next_dist=[0, 1, 2]; u=0; v=2; price=10

L8 cheapest_flight: dist = next_dist
n=3; flights=[(0, 1, 1), (1, 2, 1), (0, 2, 10)]; source=0; destination=2; k=1; dist=[0, 1, 2]; _=1; next_dist=[0, 1, 2]; u=0; v=2; price=10

Result: 2. One intermediate stop permits the cheaper two-edge route.

Why the solution is correct

Any route with at most j edges either uses at most j-1 edges or extends such a route by one final flight. The copy and edge relaxations consider exactly these alternatives. Fresh-layer reads enforce the budget regardless of flight input order. Induction proves the final bounded cost optimal.

Time and space

O((k+1)*(V+E)) time, including each distance-array copy, and O(V) auxiliary space.

Common mistakes

In-place relaxation may chain several flights within one layer. Confusing stops with edges removes or adds one legal flight.

Reasoning card

State: dist holds costs using at most the completed number of edges. next_dist begins as a copy, retaining routes that use fewer edges.

Invariant: Cost state includes both destination and resources used.

Decision to rehearse: Use layered relaxation/Bellman-Ford or state (node,stops) in a heap.

Finish: Return destination cost or -1

Transfer exercise

Return the selected flights by storing a predecessor for every budget layer, rather than one predecessor per vertex.