Understanding the Problem

This is a shortest path problem with a twist. We need to find the cheapest route between two cities, but we can use at most k intermediate stops (which means at most k + 1 edges). Standard shortest path algorithms like Dijkstra's find the cheapest path regardless of how many edges it uses. Here, a longer path might be cheaper, but we can't take it if it exceeds our stop limit.

So the question becomes: how do we find the shortest path while respecting an edge count constraint? We need to track not just the cost to reach a city, but how many stops we used to get there. A city might be reachable cheaply with 5 stops, but if k = 2, that path is useless to us.

The key insight is that we need to explore paths level by level (where each level represents one more flight taken), and we should stop exploring once we've used k + 1 flights. This naturally maps to either BFS with level tracking or a modified Bellman-Ford that runs exactly k + 1 iterations.

Key Constraints:

1 <= n <= 100 → With n up to 100, even O(n^3) would mean 1 million operations. This opens the door to approaches like Bellman-Ford without worry.
0 <= flights.length <= n * (n - 1) / 2 → At most ~5,000 edges. This is a sparse-to-moderate graph.
1 <= price_i <= 10^4 → All prices are positive, so no negative weight cycles to worry about.
0 <= k < n → k can be 0 (only direct flights) up to n-1. When k = n-1, the stop constraint effectively disappears.

Approach 1: BFS with Level Tracking

Intuition

BFS naturally explores paths level by level. If we think of each "level" as one additional flight, then after processing level 0 we've considered all direct flights from the source, after level 1 we've considered all paths with one stop, and so on. We stop after level k (which corresponds to k + 1 flights or k stops).

At each level, we look at all cities we can currently reach and try extending from them by one more flight. We track the cheapest known cost to reach each city. The trick is that we need to use the costs from the start of the current level when deciding whether to update, not costs that were just updated during this same level. Otherwise, we could chain updates within a single level and effectively take more flights than we should.

Algorithm

Build an adjacency list from the flights array.
Create a dist array of size n initialized to infinity, with dist[src] = 0.
Add src to a queue.
For each level from 0 to k (at most k + 1 levels):

Take a snapshot of the current dist array.
For each node in the queue at this level, explore its neighbors. If the cost through this node is cheaper than the neighbor's current best, update it and add the neighbor to the queue.

Return dist[dst] if it's not infinity, otherwise return -1.

Example Walkthrough

1Initialize: dist[src=0]=0, all others INF. Queue=[0]

[0, INF, INF]

1/6

Code

Complexity Analysis

Time Complexity: O(k * E). We process at most k + 1 levels. In the worst case, each level processes all edges in the graph. E is the number of flights.
Space Complexity: O(n + E). O(E) for the adjacency list, O(n) for the dist array, and the queue can hold at most O(n) nodes per level.

This approach works correctly but requires building an adjacency list and can add duplicate nodes to the queue. What if we simply iterated over all edges k + 1 times, relaxing each one?

Approach 2: Modified Bellman-Ford

Intuition

Bellman-Ford is a classic shortest path algorithm that works by relaxing all edges repeatedly. In the standard version, you run n - 1 iterations, and after iteration i, you've found the shortest paths using at most i + 1 edges. This is exactly what we need: if we run k + 1 iterations, we'll find the shortest paths using at most k + 1 edges (i.e., k stops).

But there's a subtle catch. In standard Bellman-Ford, when you relax edges within a single iteration, updates from earlier in the iteration can cascade. The fix is simple: at the start of each iteration, take a snapshot of the distance array from the previous iteration. When relaxing edges, read from the snapshot but write to the current array. This ensures each iteration only extends paths by exactly one edge.

Why does this work?

The correctness rests on a property of Bellman-Ford: after iteration i, the dist array contains the shortest paths from the source using at most i + 1 edges. By reading from prevDist (the state after iteration i - 1) and writing to dist, we guarantee that each relaxation only extends paths by exactly one edge. After k + 1 iterations, dist[dst] holds the cheapest path using at most k + 1 edges, which is at most k stops.

Algorithm

Create a dist array of size n, initialized to infinity, with dist[src] = 0.
For each iteration from 0 to k (k + 1 iterations total):

Copy dist into prevDist (snapshot of the previous iteration).
For each flight [from, to, price]:

If prevDist[from] is not infinity and prevDist[from] + price < dist[to], update dist[to].

Return dist[dst] if it's not infinity, otherwise return -1.

Example Walkthrough

1Initialize: dist[src=0]=0, all others INF

[0, INF, INF, INF]

1/6

Code

Complexity Analysis

Time Complexity: O(k E). We run k + 1 iterations, each iterating over all E flights. With k < n and E up to n(n-1)/2, this is at most O(n^3), which is fast for n <= 100.
Space Complexity: O(n). Two arrays of size n: dist and prevDist. No adjacency list needed since we iterate over the flights array directly.

Cheapest Flights Within K Stops

Understanding the Problem

Key Constraints:

Approach 1: BFS with Level Tracking

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Modified Bellman-Ford

Intuition

Algorithm

Example Walkthrough

Code

Get Premium