787. Cheapest Flights Within K Stops (Bellman-Ford, Single-Source Shortest Path with a Limited Number of Edges)¶
Edited by Charles
Medium · Python · Graph
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
This problem can be solved using a modified Bellman-Ford algorithm.
The key difference from standard Bellman-Ford is that we are only allowed to use at most k stops.
Original study notes follow, including intermediate snippets and earlier attempts.
Approach: Bellman-Ford with Limited Relaxations¶
This problem can be solved using a modified Bellman-Ford algorithm.
The key difference from standard Bellman-Ford is that we are only allowed to use at most k stops.
If a path contains k intermediate stops, then it contains at most:
Therefore, instead of performing n - 1 rounds of relaxation, we only perform:
rounds.
Store All Edges¶
We first store all flights as edges:
Each edge represents:
Since Bellman-Ford directly iterates through all edges, we do not need to build an adjacency list.
Define minCost¶
minCost[i] represents:
The minimum cost to reach city
ifromsrcusing at most the number of edges allowed by the current relaxation round.
Initially:
because we have not used any flights yet.
Why k + 1 Relaxations?¶
The problem allows at most k stops.
For example:
There are:
Therefore:
Bellman-Ford has an important property:
After 1 round → shortest paths using at most 1 edge
After 2 rounds → shortest paths using at most 2 edges
After 3 rounds → shortest paths using at most 3 edges
...
Therefore, to allow at most k stops, we perform:
This is the most important part of this problem.
At the beginning of every round:
We read values from:
but write new values into:
During relaxation:
At the end of the round:
The purpose of temp is to make sure that each Bellman-Ford round extends the path by at most one edge.
What Goes Wrong Without temp?¶
Consider:
Initially:
Suppose we directly update minCost in place.
Process 0 → 1¶
Process 1 → 2¶
Because minCost[1] was just updated in the same round, we can immediately use it:
Process 2 → 3¶
Again, minCost[2] was just updated:
This means that in one relaxation round, we traveled:
which uses 3 edges.
This destroys the meaning of:
and can violate the k-stop constraint.
Now consider the same graph:
Initially:
At the beginning of the first round:
so:
Round 1¶
Process:
We update:
so:
Now process:
The important point is that we check:
NOT:
Since:
we cannot use the newly discovered path to node 1 in the same round.
Therefore, node 2 is not updated.
After the round:
Now:
This represents paths using at most 1 edge.
Round 2¶
Create another copy:
Now:
can use:
so:
After this round:
This represents paths using at most 2 edges.
Round 3¶
Similarly:
allows:
so:
This represents paths using at most 3 edges.
Therefore:
Round 1 → at most 1 edge
Round 2 → at most 2 edges
Round 3 → at most 3 edges
...
Round k+1 → at most k+1 edges
This is exactly what we need.
Read from minCost, Write to temp¶
The key relaxation is:
if minCost[source] != float('inf') and \
minCost[source] + cost < temp[destination]:
temp[destination] = minCost[source] + cost
Notice the difference:
This is intentional.
minCost represents the results from the previous round.
temp represents the results for the current round.
Therefore:
This guarantees that one round can add at most one new edge to a path.
Why temp = minCost.copy() Instead of a New inf Array?¶
We use:
instead of:
because the problem asks for paths using at most k + 1 edges, not exactly k + 1 edges.
For example, if we already know:
after one round, that result should still be valid after the second round.
Copying:
preserves all previously discovered cheaper paths while also allowing paths using one additional edge to be discovered.
Therefore:
Early Termination¶
We use:
and whenever a better path is found:
After scanning all edges:
If no value changes during a complete relaxation round, further rounds cannot improve any shortest path.
Therefore, we can terminate early.
Complexity¶
Let:
We perform at most:
rounds.
Each round scans all E edges.
Therefore:
The minCost and temp arrays require:
space.
The edges list requires:
space.
Therefore:
Since flights itself already contains all edges, the extra algorithmic distance-array space is O(V).
Code¶
class Solution:
def findCheapestPrice(
self,
n: int,
flights: List[List[int]],
src: int,
dst: int,
k: int
) -> int:
edges = []
for u, v, w in flights:
edges.append((u, v, w))
minCost = [float('inf')] * n
minCost[src] = 0
for _ in range(k + 1):
updated = False
temp = minCost.copy()
for source, destination, cost in edges:
if (
minCost[source] != float('inf')
and minCost[source] + cost < temp[destination]
):
temp[destination] = minCost[source] + cost
updated = True
if not updated:
break
minCost = temp
return -1 if minCost[dst] == float('inf') else minCost[dst]
Key Takeaway¶
The most important idea in this problem is:
tempprevents updates from the current relaxation round from being used again in the same round.
Without temp:
With temp:
Therefore:
Since:
performing k + 1 Bellman-Ford relaxation rounds correctly enforces the constraint.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | August 31, 2026 |
Python solution¶
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
INF = float('inf')
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1):
new = dist[:]
for u, v, w in flights:
if dist[u] + w < new[v]:
new[v] = dist[u] + w
dist = new
return dist[dst] if dist[dst] != INF else -1