← Back to DSA Animator
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.