Problem statement

There are n cities and directed flights[i] = [from, to, price]. Find the cheapest price from src to dst using at most k stops (intermediate cities). Return -1 if no such route exists.

Example 1

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

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200

Example 3

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500

Constraints

• 2 <= n <= 10
• 0 <= flights.length <= 30
• 1 <= price <= 500
• 0 <= k < n

Hints for Cheapest Flights Within K Stops

1. Hint 1

   Bellman-Ford limited to k+1 edge-relaxation rounds.

2. Hint 2

   Relax from a SNAPSHOT of distances each round so paths can't use extra edges.

How to solve Cheapest Flights Within K Stops

Plain Dijkstra fails here because the cheapest route may use too many hops — cost alone is not enough state, the number of edges matters too. Bellman-Ford fits perfectly: each relaxation round extends every route by exactly one more edge, so running k + 1 rounds explores precisely the routes with at most k stops.

Approach

1. Set every distance to infinity except dist[src] = 0.
2. Repeat k + 1 times — k stops means at most k + 1 flights.
3. At the start of each round take a snapshot of the distances.
4. Relax every flight against the snapshot: dist[to] = min(dist[to], snapshot[from] + price).
5. After the rounds, return dist[dst], or -1 if it is still infinite.

Why it works

The snapshot is the crux. After round r, dist[v] is the cheapest route to v using at most r flights — relaxing against the snapshot means a route built this round can only extend a route that already existed at the end of the previous round, so it grows by exactly one edge. Relaxing against the live array would let a route grow by several edges within one round and quietly exceed the stop limit while looking cheaper.

Complexity

• Time — O(k · E)
• Space — O(V)

Pitfalls

• Relaxing in place instead of from a snapshot is the bug in this problem: it produces answers that are too cheap because they use more stops than allowed.
• k counts intermediate stops, so the number of flights is k + 1 — run one more round than you might expect.
• Skip relaxation from a node still at infinity.
• Unreachable within the limit must return -1, even if a longer route exists.

Reference solution

Python

from typing import List

def findCheapestPrice(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):
        nxt = dist[:]
        for u, v, w in flights:
            if dist[u] + w < nxt[v]:
                nxt[v] = dist[u] + w
        dist = nxt
    return -1 if dist[dst] == INF else dist[dst]

Java

public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    final int INF = 1000000000;
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {
        int[] snapshot = dist.clone();
        for (int[] f : flights) {
            if (snapshot[f[0]] != INF && snapshot[f[0]] + f[2] < dist[f[1]]) {
                dist[f[1]] = snapshot[f[0]] + f[2];
            }
        }
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

C++

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    const int INF = 1000000000;
    vector<int> dist(n, INF);
    dist[src] = 0;
    for (int round = 0; round <= k; round++) {
        vector<int> snapshot = dist;
        for (const auto& f : flights) {
            if (snapshot[f[0]] != INF && snapshot[f[0]] + f[2] < dist[f[1]]) {
                dist[f[1]] = snapshot[f[0]] + f[2];
            }
        }
    }
    return dist[dst] == INF ? -1 : dist[dst];
}

JavaScript

var findCheapestPrice = function(n, flights, src, dst, k) {
    let dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    for (let round = 0; round <= k; round++) {
        const next = dist.slice();
        for (const f of flights) {
            if (dist[f[0]] + f[2] < next[f[1]]) next[f[1]] = dist[f[0]] + f[2];
        }
        dist = next;
    }
    return dist[dst] === Infinity ? -1 : dist[dst];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium