MediumDynamic ProgrammingDepth-First SearchBreadth-First SearchGraphHeap (Priority Queue)Shortest Path

Cheapest Flights Within K Stops

1 approach, code in every language

There are `n` cities connected by some flights. Each flight is given as `flights[i] = [from, to, price]`, meaning there is a one-directional flight from city `from` to city `to` costing `price`.

Given a starting city `src`, a target city `dst`, and an integer `k`, return the cheapest total price to travel from `src` to `dst` using at most `k` stops. A "stop" is an intermediate city, so a route with `k` stops uses up to `k + 1` flights.

If no route satisfies the stop limit, return `-1`.

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

With at most 1 stop, the route 0 -> 1 -> 3 costs 700. The cheaper 0 -> 1 -> 2 -> 3 (400) uses 2 stops and is not allowed.

Example 2

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

Output: 500

No stops are allowed, so only the direct flight 0 -> 2 for 500 qualifies; 0 -> 1 -> 2 would require one stop.

Constraints

1 <= n <= 100
0 <= flights.length <= n * (n - 1) / 2
flights[i].length == 3
0 <= from_i, to_i < n
from_i != to_i
1 <= price_i <= 10^4
There is at most one flight between any ordered pair of cities.
0 <= src, dst, k < n
src != dst

Cost-Ordered Heap with Stop Budget

Pop states in increasing cost from a heap, carrying the remaining stop budget in each state; return the cost the first time the destination is popped.

Loading animation…

Intuition

This is a shortest-path problem with an extra constraint: the number of edges (stops) is bounded. Plain Dijkstra can settle a node too early with a cheap-but-stop-heavy path and then miss a pricier route that still has budget to reach the destination. So instead of finalizing nodes by cost alone, we carry the remaining stop budget inside each heap state and allow a node to be revisited when we arrive with more budget to spend. Because the heap pops by cost, the first time the destination comes off the heap its cost is the minimum achievable within the limit. A classic alternative is Bellman-Ford restricted to k + 1 relaxation rounds, which also honors the stop bound without a heap.

Algorithm walkthrough

1Build an adjacency list of outgoing flights (to, price) for every city.
2Seed a min-heap keyed on total cost with (0, src, k), where the third field is the remaining stop budget.
3Pop the cheapest state; if its node is dst, that cost is optimal under the budget, so return it.
4Skip the state if its budget is negative, or if this node was already expanded with an equal-or-larger budget (a dominated state).
5Otherwise record the budget for this node and push each neighbor with cost + price and budget - 1.
6If the heap empties without reaching dst, no route exists within k stops, so return -1.

Implementation

import heapq
from typing import List


class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        graph = [[] for _ in range(n)]
        for u, v, w in flights:
            graph[u].append((v, w))

        best = [-1] * n            # best[node] = max stop-budget seen when expanded
        heap = [(0, src, k)]       # (cost, node, stops_remaining)

        while heap:
            cost, node, stops = heapq.heappop(heap)
            if node == dst:
                return cost
            if stops < 0 or stops <= best[node]:
                continue
            best[node] = stops
            for nei, w in graph[node]:
                heapq.heappush(heap, (cost + w, nei, stops - 1))

        return -1

Time

O(E * K * log(E * K))

Space

O(V + E * K)

Each node may be re-expanded once per distinct remaining-budget value, bounding heap size; Bellman-Ford with k + 1 rounds is an O((k + 1) * E) heap-free alternative.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Limited Handoff Courier Route is our own problem on the technique behind Cheapest Flights Within K Stops: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free