LeetEye LeetEye
Hard Advanced Graphs ~5 min

Cheapest Flights Within K Stops

advanced-graphs cheapest-flights-within-k-stops

Problem

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Examples

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
0 → 1 → 3 with 1 stop costs 700.
Example 2
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
0 → 1 → 2 with 1 stop costs 200.
Key Insight

Bellman-Ford for k+1 iterations OR modified Dijkstra tracking stops.

Bellman-Ford with k+1 iterations finds shortest path using at most k+1 edges. Each iteration extends paths by one hop.

How to Approach This Problem

Pattern Recognition: When you see keywords like cheapest flights within k stops advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 Standard Dijkstra fails here because:
Answer: It ignores the stop constraint
Dijkstra prunes paths greedily. A path with more stops but lower cost might be optimal.
2 At each node, we need to know:
Answer: Cost AND number of stops
A node might be reached cheaply with many stops, or expensively with few stops. Both matter.
3 Bellman-Ford after k+1 iterations gives:
Answer: Shortest path using at most k+1 edges
Each iteration extends paths by one edge. k+1 iterations = paths of at most k+1 edges.
4 For modified Dijkstra, heap stores:
Answer: (cost, node, stops)
We need to track stops to enforce the constraint.
5 Skip processing if:
Answer: Stops exceed k
We can revisit nodes with fewer stops. Only skip if we've exceeded stop limit.

Solution

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    # Bellman-Ford with k+1 iterations
    # prices[i] = min cost to reach city i
    prices = [float('inf')] * n
    prices[src] = 0
    
    # k stops means k+1 edges
    for _ in range(k + 1):
        # Use copy to avoid using updated values in same iteration
        temp = prices.copy()
        
        for u, v, cost in flights:
            if prices[u] != float('inf'):
                temp[v] = min(temp[v], prices[u] + cost)
        
        prices = temp
    
    return prices[dst] if prices[dst] != float('inf') else -1

Complexity Analysis

Time O(k × E)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye