Cheapest Flights Within K Stops

Q: What is the time complexity of Cheapest Flights Within K Stops?

Bellman-Ford limited to k+1 rounds takes O(k · E) time for E flights, and O(n) extra space for two price arrays. A round that changes nothing hands the next round the same prices, so you can stop early.

Q: Why doesn't Dijkstra's algorithm work for Cheapest Flights Within K Stops?

Dijkstra keeps one best price per city and never revisits a settled city. Here a dearer way into a city can be the useful one, when it took fewer flights. Dijkstra works again on states (city, flights used), which multiplies the states by k+1 .

Q: Can you solve Cheapest Flights Within K Stops with BFS?

Yes. Level r holds the cities reached with exactly r flights, with their prices. Put a city on the next level only when its new price beats the best seen for it, and stop after k+1 levels. It gives the same answer as Bellman-Ford but follows only flights out of cities whose price changed.

MediumShortest paths Graphs

+10

There are n cities, numbered 0 to n-1, and a list of one way flights: flights[i] = [from, to, price] is a flight from city from to city to that costs price.

Return the lowest total price of a trip from src to dst that makes at most k stops on the way, which means at most k+1 flights. If no such trip exists, return -1.

Function

findCheapestPrice(n: integer, flights: integer-2d-array, src: integer, dst: integer, k: integer) → integer

ninteger: the number of cities
flightsinteger-2d-array: the one way flights, each as [from, to, price]
srcinteger: the city where the trip starts
dstinteger: the city where the trip ends
kinteger: the most stops allowed between src and dst
Returnsinteger: the lowest price of a trip with at most k stops, or -1

Constraints

2 ≤ n ≤ 1000
1 ≤ flights.length ≤ 4500
flights[i] = [from, to, price] with 0 ≤ from, to < n and from ≠ to
1 ≤ price ≤ 10⁴
No two flights share both from and to.
0 ≤ src, dst < n and src ≠ dst
0 ≤ k < n

Examples

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
Output: 230
Explanation: One stop allows two flights: 0 → 1 → 3 costs 50 + 180 = 230 and 0 → 2 → 3 costs 200 + 50 = 250. The cheaper 0 → 1 → 2 → 3 makes two stops.

Input: n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
Output: 150
Explanation: Two stops allow three flights, so 0 → 1 → 2 → 3 is allowed now, and it costs 50 + 50 + 50 = 150.

Follow-up

How would you return the cities on the cheapest trip as well as its price?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

This is a shortest path with a limit on the number of flights. Dijkstra's algorithm on cities alone fails, because the cheapest way into a city may use up stops the rest of the trip needs. Bellman-Ford fits the limit: round r finds the cheapest price with at most r flights, so you run k+1 rounds.

Try every route with at most k+1 flights

Correct, but does not finish on the largest tests

Intuition

Walk every route from src with a stack of (city, price, flights used). A route that reaches dst records its price and ends, since every price is positive. A route with k+1 flights is dropped; any other is extended by every flight out of its city. Every allowed trip gets built, so the best recorded price is right.

The routes grow like d to the power k+1, for d flights out of a city. With 4 flights per city and k = 29, that is 4^30 ≈ 1.2 × 10^18 routes.

Algorithm

Group the flights by departure city.
Push (src, 0, 0): city, price so far, flights taken.
Pop a route. If its city is dst, keep its price if it is the best so far.
Otherwise, if it has taken fewer than k+1 flights, push one longer route per flight out of its city.
When the stack is empty, return the best price, or -1 if none reached dst.

def findCheapestPrice(n, flights, src, dst, k):
    out = [[] for _ in range(n)]
    for a, b, price in flights:
        out[a].append((b, price))
    best = -1
    # Each entry is a route in progress: (city, price so far, flights taken).
    stack = [(src, 0, 0)]
    while stack:
        city, cost, used = stack.pop()
        if city == dst:
            if best == -1 or cost < best:
                best = cost
            continue
        # k stops allow at most k+1 flights.
        if used == k + 1:
            continue
        for nxt, price in out[city]:
            stack.append((nxt, cost + price, used + 1))
    return best

Bellman-Ford limited to k+1 rounds

Intuition

Let cost[c] be the cheapest price to reach city c with at most r flights. At r = 0 only src is reachable, at price 0. A trip to a with at most r flights, followed by a flight a → b, is a trip to b with at most r+1, so each round offers cost[a] + price to b for every flight. After k+1 rounds, cost[dst] is the answer.

Each round reads last round's prices and writes into a copy, so a price set during a round cannot feed another flight in the same round. In the first example with k = 1, city 2 drops to 100 in round 2, but no round is left to fly on to city 3 for 150.

Each round reads every flight once: O(k · E) time for E flights, and O(n) space for the two arrays.

Algorithm

Set cost[src] = 0 and every other cost to infinity.
Repeat k+1 times: copy cost into next.
For every flight [a, b, price] where cost[a] is finite, if cost[a] + price < next[b], set next[b] = cost[a] + price.
Replace cost with next, and stop early if nothing changed.
Return cost[dst], or -1 if it is still infinity.

def findCheapestPrice(n, flights, src, dst, k):
    INF = float("inf")
    # cost[c]: the cheapest price to reach city c with the flights allowed so far.
    cost = [INF] * n
    cost[src] = 0
    # Each round allows one more flight; k stops means k+1 flights.
    for _ in range(k + 1):
        # Read last round's prices and write into a copy,
        # so one round can never chain two flights.
        nxt = cost[:]
        changed = False
        for a, b, price in flights:
            if cost[a] != INF and cost[a] + price < nxt[b]:
                nxt[b] = cost[a] + price
                changed = True
        cost = nxt
        if not changed:
            break
    return -1 if cost[dst] == INF else cost[dst]

Pitfalls and edge cases

Counting stops as flights. k stops means k+1 flights and k+1 rounds.
Updating in place. With 0 → 1, 1 → 2, 2 → 3 for 1 each, in that order, plus 0 → 3 for 500 and k = 0, one round chains three flights and returns 3, not 500.
Running plain Dijkstra on cities. With 0 → 1 and 1 → 2 for 1 each, 0 → 2 for 40, 2 → 3 for 1 and k = 1, it settles city 2 at 2 after two flights and misses 0 → 2 → 3 for 41.
Flying out of an unreached city. With infinity as the largest int, cost[a] + price wraps negative in 32 bits. Check that cost[a] is finite first.

Frequently asked questions3

What is the time complexity of Cheapest Flights Within K Stops?

Bellman-Ford limited to k+1 rounds takes O(k · E) time for E flights, and O(n) extra space for two price arrays. A round that changes nothing hands the next round the same prices, so you can stop early.

Why doesn't Dijkstra's algorithm work for Cheapest Flights Within K Stops?

Dijkstra keeps one best price per city and never revisits a settled city. Here a dearer way into a city can be the useful one, when it took fewer flights. Dijkstra works again on states (city, flights used), which multiplies the states by k+1.

Can you solve Cheapest Flights Within K Stops with BFS?

Yes. Level r holds the cities reached with exactly r flights, with their prices. Put a city on the next level only when its new price beats the best seen for it, and stop after k+1 levels. It gives the same answer as Bellman-Ford but follows only flights out of cities whose price changed.

def findCheapestPrice(n, flights, src, dst, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

n = 4
flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]
src = 0
dst = 3
k = 1

Expected Output