Cheapest Flights Within K Stops

Explanation & Solution

Description

You are given n cities connected by some number of flights. You are given an array flights where flights[i] = [from, to, price] represents a flight from city from to city to with cost price.

You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

A stop is any intermediate city between src and dst — the source and destination themselves do not count as stops.

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

Explanation: The cheapest path with at most 1 stop is 0 → 1 → 3 with cost 100 + 600 = 700. The path 0 → 1 → 2 → 3 costs 400 but uses 2 stops, which exceeds k = 1.

Constraints

1 <= n <= 100
0 <= flights.length <= n * (n - 1) / 2
flights[i].length == 3
0 <= from, to < n
from != to
1 <= price <= 10000
0 <= src, dst, k < n
src != dst

Approach

Graphs pattern

1. Initialize Distance Array

Create a prices array of size n, filled with Infinity
Set prices[src] = 0 since the cost to reach the source is zero

2. Iterate k + 1 Times (Bellman-Ford Relaxation)

We allow at most k stops, which means at most k + 1 edges
For each iteration:
Create a copy temp of the current prices array
This copy is critical — it prevents using a path updated in the same iteration, which would allow more edges than intended

3. Relax All Edges

For each flight [from, to, price]:
If prices[from] is Infinity, skip — we cannot reach from yet
If prices[from] + price < temp[to], update temp[to]
We read from prices (previous iteration) and write to temp (current iteration)

4. Update Prices

After processing all edges, set prices = temp
This ensures each iteration only extends paths by one edge

5. Return the Result

If prices[dst] is still Infinity, no valid route exists — return -1
Otherwise, return prices[dst] as the cheapest price

Key Insight

Standard Bellman-Ford relaxes edges n - 1 times to find shortest paths. Here, we only relax k + 1 times because we are limited to at most k stops (k + 1 edges). The critical detail is copying the prices array before each iteration — without this, a single iteration could chain multiple edges together, violating the stop constraint. This modified Bellman-Ford runs in **O((k + 1) * E)** time where E is the number of flights.

Visualization

Input:

Bellman-Ford4 nodes, 5 edges

output—

Press play to start bellman-ford

CurrentQueuedVisited

7 steps

Solution Code

Word Ladder