DSA AnimatorDSA animations
Cheapest Flights Within K Stops LC #787 Medium Graph · Bellman-Ford · K Rounds
Problem

n cities, flights [from,to,price]. Start at src, reach dst with at most k stops. Return cheapest price or -1.

Example
Input: n=4, src=0, dst=3, k=1, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
Output: 700
Try Examples
Custom: n / flights (u-v-w) / src / dst / k
Approach
Bellman-Ford (k+1 rounds)
Each round = one more hop. tmp=dist.clone() prevents same-round cascading. dist[dst]=answer.
Graph & dist[]
Load an example.
Variables
Round
—
dist[dst]
—
Updated
—
Result
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
dist[src]=0, others=∞
2
k+1 rounds: relax all edges (tmp=clone)
3
Return dist[dst] or -1
Time
O(k·E)
Space
O(n)
Why k+1 Rounds

Round i = paths with ≤i edges. Clone ensures we only use prev-round dist when relaxing. Stops same-round multi-hop.

How to solve Cheapest Flights Within K Stops

LeetCode 787 · Medium · Graph · Pattern: Bellman-Ford with Rounds

Why the obvious approach is slow

Plain Dijkstra finds the cheapest route, but it ignores the limit on stops. We need to control how many flights a route uses.

The key idea

At most k stops means at most k plus 1 flights. Bellman Ford relaxes every flight once per round, and after r rounds it knows the best prices using at most r flights. So run exactly k plus 1 rounds. In each round, read prices from a copy of the previous round, so one round can never chain two flights together.

Remember

Round r of Bellman Ford means at most r edges. Relax from a copy, so a single round never uses two flights.

Run the animation above on your own input, or watch the 2:14 video explanation of Cheapest Flights Within K Stops with a dry run and Java code.

More Graph problems