Problem Overview
LeetCode 787 — Cheapest Flights Within K Stops — gives you n cities, a list of flights as [from, to, price] triples, a source city src, a destination city dst, and an integer k. Return the cheapest price from src to dst with at most k stops. If no such route exists, return -1.
The constraint of at most k stops means the path can have at most k+1 edges (k intermediate cities plus the destination). Standard Dijkstra finds the cheapest path overall, but it might use more than k stops. We need to incorporate the stop limit into our algorithm.
Three approaches work: Bellman-Ford limited to k+1 relaxation rounds, BFS processing level by level up to k+1 levels, and modified Dijkstra with a (cost, node, remainingStops) state. Each has different tradeoffs in clarity and efficiency.
- Input: n cities, flights [from, to, price], src, dst, k stops
- At most k stops means at most k+1 edges in the path
- Return cheapest price or -1 if no valid route
- Standard shortest path algorithms need modification
- Multiple valid approaches: Bellman-Ford, BFS, Dijkstra
Approach 1: Bellman-Ford with K+1 Rounds
Standard Bellman-Ford relaxes all edges V-1 times. Here we only need k+1 relaxation rounds (k stops = k+1 edges). Initialize dist[src] = 0, all others = infinity. Run k+1 rounds of relaxation over all edges.
Critical detail: at each round, use a COPY of the previous round's distances when relaxing. If you update in-place, a single round might propagate through multiple edges, effectively allowing more than one additional stop per round.
After k+1 rounds, dist[dst] is the cheapest price with at most k stops. If dist[dst] is still infinity, return -1. This approach is clean, easy to implement, and has O(k * E) time complexity.
Copy Before Relaxing
The most common bug is not copying the distance array before each round. Without copying, relaxations chain within a single round — a path of length 3 could be discovered in round 1. Always use prev = dist.copy() at the start of each round.
Approach 2: BFS Level by Level
Build an adjacency list from the flights. BFS from src, processing one level (one stop) at a time. Maintain a cost array where cost[node] is the cheapest known price to reach that node. Process at most k+1 levels.
At each level, for each node in the current queue, explore its neighbors. If the new cost through this edge is cheaper than cost[neighbor], update and add the neighbor to the next level's queue. After k+1 levels, return cost[dst].
To avoid processing the same node multiple times at the same cost, only enqueue a neighbor if the new cost is strictly less than its current recorded cost. This pruning keeps the BFS efficient while respecting the stop limit.
Approach 3: Modified Dijkstra
Use a min-heap with entries (cost, node, stopsUsed). Start with (0, src, 0). Pop the cheapest entry. If node == dst, return cost. If stopsUsed > k, skip. Otherwise, for each neighbor, push (cost + price, neighbor, stopsUsed + 1).
Unlike standard Dijkstra, we cannot simply skip a node once visited because a more expensive path with fewer stops might lead to a cheaper result later. Track the minimum stops used to reach each node; only skip if we have reached this node with fewer or equal stops before.
This approach can be less efficient than Bellman-Ford for dense graphs because the heap may grow large. However, for sparse graphs it is fast due to early termination when dst is first popped.
Why Not Standard Dijkstra?
Standard Dijkstra marks nodes as visited after first extraction. But here a node might be reachable cheaply with many stops and expensively with few stops. We need to track both dimensions (cost AND stops), so the visited check must account for stops remaining.
Step-by-Step Walkthrough
Consider n=4, flights=[[0,1,100],[1,2,100],[2,3,100],[0,2,500]], src=0, dst=3, k=1. Bellman-Ford: dist=[0, inf, inf, inf]. Round 1: edge 0→1: dist[1]=100. Edge 0→2: dist[2]=500. (Copy prevents 1→2 from updating in same round.) dist=[0, 100, 500, inf].
Round 2 (k+1=2): copy prev=[0,100,500,inf]. Edge 1→2: 100+100=200 < 500, dist[2]=200. Edge 2→3: 500+100=600, dist[3]=600. Edge 0→1: 100 (no change). Edge 0→2: 500 (no change). dist=[0, 100, 200, 600]. Return dist[3]=600.
The cheapest path with at most 1 stop is 0→2→3 costing 500+100=600. The path 0→1→2→3 costs 300 but uses 2 stops, exceeding k=1. Without the stop limit, 300 would be optimal. The Bellman-Ford correctly limits to k+1=2 edges.
Implementation in Python and Java
Python Bellman-Ford: dist = [float("inf")] * n. dist[src] = 0. For _ in range(k+1): prev = dist[:]. For u, v, w in flights: if prev[u] < float("inf"): dist[v] = min(dist[v], prev[u] + w). Return dist[dst] if dist[dst] < float("inf") else -1.
Java Bellman-Ford: int[] dist = new int[n], Arrays.fill(dist, Integer.MAX_VALUE). dist[src] = 0. k+1 rounds with int[] prev = dist.clone(). Same relaxation logic. Return dist[dst] == MAX_VALUE ? -1 : dist[dst].
The BFS approach in Python uses a deque with level processing. Modified Dijkstra uses heapq with (cost, node, stops) tuples. All three are accepted on LeetCode. Bellman-Ford is the simplest and most commonly expected in interviews.
YeetCode Flashcard Tip
Cheapest Flights is the quintessential constrained shortest path problem. Practice it alongside Network Delay Time and Swim in Rising Water on YeetCode to master graph shortest path variants.
Complexity Analysis
Bellman-Ford: O(k * E) time where E is the number of flights. Each of k+1 rounds relaxes all E edges. Space is O(V) for the distance array plus O(V) for the copy. With constraints V <= 100, E <= V^2 = 10,000, k <= 100, worst case is 1,000,000 operations.
BFS: O(V * E) time in the worst case since nodes can be re-enqueued at different levels. With pruning, it is often faster in practice. Space is O(V * k) for the queue across levels.
Modified Dijkstra: O(E * k * log(E * k)) time due to heap operations. Each edge can generate a heap entry at each stop count. In practice, early termination and pruning make it competitive.