LeetCode #787 Medium

Cheapest Flights Within K Stops

Given flights [from, to, price], find the cheapest route from src to dst using at most k stops, or -1 if none exists.

graphsshortest-pathbellman-fordbfs

Open on LeetCode ↗

02

Intuition

💡

The reflex is Dijkstra, and here it is wrong. Dijkstra commits to the cheapest known cost for a city and never revisits it — but under a stop limit, an expensive route with few stops can be the only usable one, and Dijkstra will have already discarded it. The stop count is a second dimension the algorithm does not track. The fix is to relax the graph in rounds: after round i, the distance array holds the cheapest cost reachable using at most i flights. Run k + 1 rounds and read off the destination.

03

Approach

1

See concretely why Dijkstra fails

Consider a graph where reaching city C costs 100 via a two-flight path and 500 via one direct flight, with k = 0 (no stops allowed). Dijkstra finalises C at 100 and never reconsiders it, so it either returns 100 — which violates the stop limit — or, with an added stop check, discards the only valid route. The problem is that cost alone is not enough state; the number of flights used matters too.

2

Relax in rounds, one flight per round

This is Bellman-Ford with a bounded iteration count. Initialise dist[src] = 0 and everything else to infinity. In each round, examine every edge and relax it. After round 1 the array holds the best cost using at most one flight, after round 2 at most two, and so on. Since k stops means at most k + 1 flights, run exactly k + 1 rounds.

3

Use a snapshot of the previous round

This is the detail that makes or breaks the solution. Within a round, all relaxations must read from the previous round's array, not the one being written. If you update in place, a chain of edges can be traversed inside a single round, quietly using more flights than the round number allows and producing routes that violate the stop limit. Copy the array at the start of each round and read from the copy. Cost: O(k x E).

04

Solution & live demo

python

▶1class Solution:
▶2    def findCheapestPrice(self, n, flights, src, dst, k):
▶3        INF = float('inf')
▶4        dist = [INF] * n
▶5        dist[src] = 0
▶6        for _ in range(k + 1):
▶7            nxt = dist[:]
▶8            for u, v, w in flights:
▶9                if dist[u] != INF and dist[u] + w < nxt[v]:
▶10                    nxt[v] = dist[u] + w
▶11            dist = nxt
▶12        return -1 if dist[dst] == INF else dist[dst]

05

Edge cases

k == 0

One round runs, so only direct flights are considered — exactly right, since zero stops means one flight.

Destination unreachable within the limit

The entry stays at infinity after all rounds and -1 is returned.

src == dst

The distance is 0 from initialisation and no relaxation improves it.

Cycles in the graph

Harmless. The bounded round count prevents any route from using more than k + 1 edges, so cycles cannot be exploited or looped indefinitely.

06

Complexity

Time

O(k x E)

Space

O(n)

Two distance arrays of size n. The snapshot copy per round is what enforces the flight limit; updating in place breaks correctness.