Cheapest Flights Within K Stops

mediumAdvanced Graphs (Dijkstra / MST)45 stepsJava · Python · C++

Find the cheapest flight from src to dst with at most k stops (k + 1 flights). Run Bellman-Ford for k + 1 rounds; each round relaxes every flight once, using a copy of the previous round's prices so a round adds at most one more flight.

▶ Watch the animated trace

Traced 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 → 700. Original problem: neetcode.io/problems/cheapest-flight-path

Complexity

BestO(k·E)

AverageO(k·E)

WorstO(k·E)

SpaceO(n)

k + 1 rounds over all flights.

Key idea

After round i, price[v] is the cheapest cost using at most i flights.
Relax from the previous round's copy, or a round could chain several flights.
Plain Dijkstra fails because a cheaper path may use too many stops.

Common mistakes

Updating prices in place lets one round use multiple flights.
Treating k as the number of flights instead of stops.

Solution

Java

int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] price = new int[n];
    Arrays.fill(price, Integer.MAX_VALUE);
    price[src] = 0;
    for (int round = 0; round <= k; round++) {
        int[] next = price.clone();
        for (int[] f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (price[u] != Integer.MAX_VALUE && price[u] + w < next[v]) next[v] = price[u] + w;
        }
        price = next;
    }
    return price[dst] == Integer.MAX_VALUE ? -1 : price[dst];
}

Python

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    price = [float("inf")] * n
    price[src] = 0
    for _ in range(k + 1):
        nxt = price[:]
        for u, v, w in flights:
            if price[u] + w < nxt[v]: nxt[v] = price[u] + w
        price = nxt
    return -1 if price[dst] == float("inf") else price[dst]

C++

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    vector<int> price(n, INT_MAX);
    price[src] = 0;
    for (int round = 0; round <= k; round++) {
        vector<int> next = price;
        for (auto& f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (price[u] != INT_MAX && price[u] + w < next[v]) next[v] = price[u] + w;
        }
        price = next;
    }
    return price[dst] == INT_MAX ? -1 : price[dst];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Stop limit forces the pricier route Zero stops means the direct flight only.	`n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0`	`500`
Enough stops One stop through 1 is cheaper.	`same flights, k = 1`	`200`
Unreachable No flights at all.	`n = 2, flights = [], src = 0, dst = 1, k = 1`	`-1`