DSA sheet · Graphs · Dijkstra pattern

Cheapest Flights Within K Stops

This looks like plain Dijkstra (cheapest route from src to dst), but there's a twist: you may make at most k stops. That one limit breaks the usual "keep only the cheapest arrival" rule, because a more expensive arrival with fewer stops can be the only one that still reaches the destination in time. The teacher first solves it with a min-heap (correct, but it ran out of memory on LeetCode), then shows that a plain BFS queue is enough here and is accepted. This page also adds a third, round-by-round version (Bellman-Ford style), which has the cleanest guarantee.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Min-heap with (cost, node, stops), and why cost alone is wrong
• Part B · Plain BFS queue (her accepted solution)
• Part C · Bellman-Ford style rounds (extra)
• Part D · Revision page

Part 0 · Before starting

Directed, weighted graph

Cities are nodes, flights are edges. A flight [from, to, price] is a directed edge (one way: a flight from 0 to 1 does not mean there's one from 1 to 0) with a weight (the price). The cost of a trip is the sum of its flight prices.

Adjacency list

n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]

graph = [[] for _ in range(n)]
for u, v, price in flights:
    graph[u].append((v, price))      # one way only

print(graph)   # [[(1, 100)], [(2, 100), (3, 600)], [(0, 100), (3, 200)], []]

Stops vs flights

A stop is a city you land in between the start and the destination. The start and the destination don't count, the same way the station you leave from and the station you arrive at aren't "stops" on a train trip.

  0 ——→ 1 ——→ 2 ——→ 3
        ^     ^
      stop  stop        3 flights = 2 stops

So flights = stops + 1. "At most k stops" means "at most k + 1 flights". In the code, the teacher's counter (she calls it stops) is really the number of flights taken so far: 0 at src, +1 for every flight. A node reached with counter ≤ k may still take one more flight; a node reached with counter k + 1 may not.

BFS layers, visited, and Dijkstra (quick recap)

• BFS with a queue (collections.deque) goes level by level: all nodes 1 flight away, then 2 flights away… A visited array stops it from going round cycles. In unweighted graphs, the level is the shortest distance.
• With prices (weights), fewer flights isn't always cheaper, so plain BFS with visited fails. Dijkstra replaces the queue with a min-heap (always expand the cheapest so far) and replaces visited with "go again only if cheaper". See the Dijkstra page for the full story and a picture of BFS going wrong.
• In Python the heap is heapq: heappush, heappop, and tuples are ordered by their first item, so (cost, node, stops) sorts by cost.

This problem adds a second number per route, the stops. Dijkstra's "keep only the cheapest" rule thinks about cost only. That's exactly where it goes wrong here (Part A, step 4).

Part A · Min-heap with (cost, node, stops)

LeetCode 787

1The question in simple words

n cities, numbered 0 to n−1. flights[i] = [from, to, price]. Given src, dst and k, return the cheapest price from src to dst using at most k stops. If there's no such route, return −1.

The teacher's picture (rebuilt from the routes and totals she reads out), with src = 0, dst = 3, k = 2:

          100
   (0) ————————→ (1)
    |            /
 400|       200 /
    ↓          ↙
   (2) ——————500——————→ (3)
     \                  ↑
   100\                 |100
       ↘                |
        (4) ————————————┘

The overall cheapest route (500) is not allowed. The answer is 600.

2What the constraints tell us

• n ≤ 100, at most n(n−1)/2 flights → about 5000 edges.
• k < n → k can be up to about 100.
• Prices up to 10⁴. Even 100 flights × 10⁴ = 10⁶, far below the int limit (about 2·10⁹). Safe (and Python ints never overflow anyway).
• Prices are positive, so heap ideas are allowed.
• k × E ≈ 100 × 5000 = 5·10⁵. She uses this number at the end to explain the memory error.

3Intuition

Do Dijkstra, but let each heap entry also carry how many flights it has used. The heap still pops the cheapest entry first, so the first time dst is popped, that's the cheapest allowed price. Entries that have used up their flights are not expanded any more.

The big change from Dijkstra: don't throw away an arrival just because it is more expensive, if it used fewer stops. It may be the only one with enough stops left to finish.

4Building the logic from her examples

What goes into the heap? → (cost, node, stops)

• cost first, so the min-heap orders by price;
• node, to know where we are and whose flights to look at;
• stops: without it, when we land somewhere we can't tell whether we're still allowed to fly on. Her example: arriving at a non-destination city having already used up the allowed stops means the next flight would break the rule, so we stop there.

Start: (0, src, 0) and dist[src] = 0. Each flight adds the price to cost and 1 to stops.

Rule 1: popping dst → return the cost right away

The heap only ever contains allowed routes (we never push a route with too many flights). It pops them cheapest first. So the first popped entry for dst is the cheapest allowed route. Return it; no need to empty the heap. In her words, in the best or average case you finish early instead of exploring everything.

Rule 2: too many flights → don't expand

If we pop a node that is not dst and stops > k (we've already taken k + 1 flights), one more flight would make k + 1 stops. Skip it: continue.

Rule 3, the new one: keep a pricier arrival if it used fewer stops

This is the heart of the problem. Let's run plain Dijkstra's push rule, "push only if new_cost < dist[nei]", on her picture (this is her first board run):

The arrival at node 4 with cost 500 but only 2 flights was thrown away because dist[4] already held 400. But that 400 came with 3 flights and is stuck: it can't fly to 3. The 500 one could have flown on to 3 for a total of 600 with 2 stops. Wrong answer.

Her fix (the "change one line" part of the video): even if the new cost is not smaller, still push it if this route has stops left to continue. "Greater now" doesn't mean "useless later".

  if new_cost < dist[nei]  or  stops < k:
      push (new_cost, nei, stops + 1)
      dist[nei] = min(dist[nei], new_cost)

So why exactly does plain Dijkstra fail here?

Dijkstra's rule "once I know a cheaper way to X, every pricier way to X is useless" is true when cost is the only thing that matters. Here a route has two numbers, cost and stops used. A route can be worse in cost but better in stops, and then neither one beats the other.

And if you ignore stops completely, plain Dijkstra returns 500 (route 0→1→2→4→3), which uses 3 stops and isn't allowed. So plain Dijkstra fails in both directions: without a stop check it breaks the limit, and with a stop check but "cheapest only" pruning it gives up on routes it needed.

import heapq

def dijkstra_cost_only(n, flights, src, dst, k):
    graph = [[] for _ in range(n)]
    for u, v, price in flights:
        graph[u].append((v, price))
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src, 0)]
    while pq:
        cost, node, stops = heapq.heappop(pq)
        if node == dst:
            return cost
        if cost > dist[node] or stops > k:
            continue
        for nei, price in graph[node]:
            if cost + price < dist[nei]:        # BUG: pricier-but-fewer-stops routes are lost
                dist[nei] = cost + price
                heapq.heappush(pq, (cost + price, nei, stops + 1))
    return -1

her = [[0, 1, 100], [0, 2, 400], [1, 2, 200], [2, 3, 500], [2, 4, 100], [4, 3, 100]]
print(dijkstra_cost_only(5, her, 0, 3, 2))   # 800  (wrong: the answer is 600)

5Approach steps

1. Build a directed adjacency list.
2. dist = [inf] * n, dist[src] = 0, heap = [(0, src, 0)].
3. Pop the cheapest (cost, node, stops).
4. If node is dst → return cost.
5. If stops > k → continue (no flights left).
6. For each flight (nei, price): new_cost = cost + price. If new_cost < dist[nei] or stops < k: push (new_cost, nei, stops + 1) and set dist[nei] = min(dist[nei], new_cost).
7. Heap empty and dst never popped → return −1.

6Code (Python)

import heapq

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        graph = [[] for _ in range(n)]
        for u, v, price in flights:
            graph[u].append((v, price))             # directed

        dist = [float('inf')] * n
        dist[src] = 0
        pq = [(0, src, 0)]                          # (cost, node, flights used)

        while pq:
            cost, node, stops = heapq.heappop(pq)
            if node == dst:                         # first pop of dst = cheapest allowed
                return cost
            if stops > k:                           # no flights left from here
                continue
            for nei, price in graph[node]:
                new_cost = cost + price
                if new_cost < dist[nei] or stops < k:   # cheaper, OR still has stops to spare
                    heapq.heappush(pq, (new_cost, nei, stops + 1))
                    dist[nei] = min(dist[nei], new_cost)
        return -1

7Code line by line

8Dry run: heap and dist after every pop

Her picture, src 0, dst 3, k = 2. Heap entries are (cost, node, stops), shown in sorted order. dist = [node0 … node4].

Compare pop 4 with the wrong board run in step 4: the or stops < k keeps (500, 4, 2) alive, and that's the entry that finds 600.

  (400, 4, 3)  cheap, but stuck
  (500, 4, 2)  pricier, can still fly

  (0) —400—→ (2) —100—→ (4) —100—→ (3)
  flights 3, stops 2, total 600

9Complexity & why LeetCode said "Memory Limit Exceeded"

• Her count: one node can enter the heap once per possible number of stops, so up to about k × E entries, each push/pop costing log. Time about O(kE · log(kE)), space O(kE). With k ≈ 100 and E ≈ 5000 that's about 5·10⁵ entries.
• The cause, in her words: the or stops < k pushes routes even when they are not cheaper, so the heap fills up with entries. On LeetCode this code got Memory Limit Exceeded. The logic isn't wrong; the constraints are what make it fail.

import heapq

def cheapest_heap_pruned(n, flights, src, dst, k):
    graph = [[] for _ in range(n)]
    for u, v, price in flights:
        graph[u].append((v, price))
    fewest = [float('inf')] * n             # fewest flights a node was expanded with
    pq = [(0, src, 0)]
    while pq:
        cost, node, stops = heapq.heappop(pq)
        if node == dst:
            return cost
        if stops > k or stops >= fewest[node]:   # out of flights, or cheaper AND not-more-stops route already used
            continue
        fewest[node] = stops
        for nei, price in graph[node]:
            heapq.heappush(pq, (cost + price, nei, stops + 1))
    return -1

her = [[0, 1, 100], [0, 2, 400], [1, 2, 200], [2, 3, 500], [2, 4, 100], [4, 3, 100]]
print(cheapest_heap_pruned(5, her, 0, 3, 2))   # 600

Part B · Plain BFS queue (her accepted solution)

1The question

Same question. The idea: we don't really need the heap. The real limit here is the number of flights, and a plain BFS queue already handles routes in order of flights: first everything 1 flight away, then 2 flights, and so on. So explore all allowed routes and read dist[dst] at the end.

2What the constraints tell us

k × E ≈ 5·10⁵ → an O(k × E) method with no log and no pile-up of entries fits easily in both time and memory.

3Intuition

Think of BFS levels as "number of flights taken". Level 1 = cities 1 flight from src, level 2 = 2 flights, …, and we stop expanding after level k + 1. Along the way, dist[x] keeps the cheapest price seen for x. Because the queue hands out routes in order of flights used, any route that arrives later has used at least as many flights as earlier ones. So if it's not cheaper either, it's worse in both ways and safe to drop. That's why "push only if cheaper" is correct again here, while it wasn't in the heap version (the heap hands routes out by cost, so a fewer-flights route can arrive later).

4What changes from Part A (her edits on screen)

1. The heap becomes a normal queue (deque, first in, first out).
2. Remove "if node == dst: return cost". With a normal queue the first arrival at dst is the one with the fewest flights, not the cheapest. A later route with more flights may be cheaper (LeetCode example below). So we explore everything allowed and read dist[dst] at the end.
3. Keep "if stops > k: continue". We still must not expand routes that are out of flights.
4. Remove the or stops < k. Push only if new_cost < dist[nei], and then set dist[nei] = new_cost directly (it's smaller, so no min needed).
5. At the end: dist[dst] still infinity → −1, else dist[dst].

5Approach steps

1. Build the directed adjacency list.
2. dist = [inf] * n, dist[src] = 0, queue = [(0, src, 0)].
3. Pop from the front: (cost, node, stops). If stops > k → continue.
4. For every flight (nei, price): if cost + price < dist[nei] → update dist[nei] and append (cost + price, nei, stops + 1).
5. Return −1 if dist[dst] is infinity, else dist[dst].

6Code (Python)

from collections import deque

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

        dist = [float('inf')] * n
        dist[src] = 0
        queue = deque([(0, src, 0)])                # (cost, node, flights used)

        while queue:
            cost, node, stops = queue.popleft()
            if stops > k:                           # out of flights
                continue
            for nei, price in graph[node]:
                new_cost = cost + price
                if new_cost < dist[nei]:            # cheaper than anything seen
                    dist[nei] = new_cost
                    queue.append((new_cost, nei, stops + 1))

        return -1 if dist[dst] == float('inf') else dist[dst]

7Code line by line

8Dry run: queue and dist after every pop

Her picture (src 0, dst 3, k = 2)

dist[3] = 600 ✓. The 2-flight arrival at node 4 (500, pop 3) was written before the cheaper 3-flight one (400, pop 4), so it wasn't blocked.

LeetCode example 1 (why we can't return at the first dst arrival)

  flights: 0→1 (100), 1→2 (100), 2→0 (100), 1→3 (600), 2→3 (200)
  src 0, dst 3, k = 1  (at most 2 flights)

1. pop (0,0,0) → 1 gets 100. queue: (100,1,1).
2. pop (100,1,1) → 2 gets 200, 3 gets 700. queue: (200,2,2) (700,3,2).
3. pop (200,2,2) → stops 2 > 1, skip. (Its route 0→1→2→3 = 400 would use 2 stops.)
4. pop (700,3,2) → skip. Queue empty. dist[3] = 700 ✓.

Here the first arrival happens to be the answer, but in her picture the first arrival at 3 was 900 (pop 3) and the answer turned out to be 600 (pop 6). That's why the BFS version must not return early.

9Complexity & remember

• Time about O(k × E): there are k + 1 levels, and in each level the flights get scanned. No log, because there's no heap.
• Space about O(k × E) in the worst case for the queue (usually much less), plus O(V + E) for the graph.
• Her trade-off: the heap version can finish early (best case, dst is popped almost at once) but pays a log and piles up entries. The BFS version always explores every allowed route, but each step is cheap. With these constraints BFS wins and is accepted.

To be exact: in an unlucky order a node can be improved and queued more than once in the same level, so k × E is a typical figure rather than a hard cap. Part C gives a version where (k + 1) × E is guaranteed.

Part C · Bellman-Ford style rounds (extra)

Not in the video, but it's the classic answer for "shortest path with at most k + 1 edges", and it makes the BFS idea completely strict.

1Idea

Keep dist = "cheapest price using at most r flights". Start with r = 0: only src is 0. Each round allows one more flight: for every flight u → v, try dist[u] + price for v. After k + 1 rounds, dist[dst] is the cheapest price with at most k + 1 flights.

2The one trap: copy the array each round

Read from the old round and write into a copy. If you updated in place, a round could use a value written earlier in the same round and chain two flights in one round, breaking the count.

3Steps

1. dist = [inf] * n, dist[src] = 0.
2. Repeat k + 1 times: new = dist[:]; for each flight u → v: if dist[u] + price < new[v], set new[v]. Then dist = new.
3. Return −1 if dist[dst] is infinity, else dist[dst].

4Code (Python)

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        dist = [float('inf')] * n
        dist[src] = 0
        for _ in range(k + 1):                      # one round = one more flight allowed
            new = dist[:]                           # read old, write copy
            for u, v, price in flights:
                if dist[u] + price < new[v]:
                    new[v] = dist[u] + price
            dist = new
        return -1 if dist[dst] == float('inf') else dist[dst]

5Dry run on her picture (k = 2 → 3 rounds)

Round 3 computes dist[3] from round 2's values: min(900, 300 + 500, 500 + 100) = 600. It reads the 2-flight 500 for node 4, not round 3's fresh 400 (which used 3 flights). That's the copy at work.

6Complexity

Time O((k + 1) × E) exactly, space O(n). Short, strict, and no graph building needed.

Part D · Revision page

s = Solution()
her = [[0, 1, 100], [0, 2, 400], [1, 2, 200], [2, 3, 500], [2, 4, 100], [4, 3, 100]]
print(s.findCheapestPrice(5, her, 0, 3, 2))                                                            # 600
print(s.findCheapestPrice(5, her, 0, 3, 3))                                                            # 500
print(s.findCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1))  # 700
print(s.findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1))                         # 200
print(s.findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0))                         # 500
print(s.findCheapestPrice(3, [[0, 1, 100]], 0, 2, 1))                                                   # -1

Based on this video: Cheapest Flights Within K Stops