Dijkstra with state: shortest path under an extra limit

In this article

1. Before you start
2. Why interviewers ask this
3. Dijkstra with state from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one pattern in the coding interview questions guide, and it builds on plain shortest-path search.

Why interviewers ask this

A question such as the LeetCode problem Cheapest Flights Within K Stops looks like a plain shortest-path task. It tests whether a candidate notices that the extra limit changes what a "node" is, instead of bolting a counter onto the textbook algorithm.

A weak answer runs plain Dijkstra and then tries to patch in the limit with an if, or reaches for a counter that never makes it into the distance table. A strong answer states the state first, says what the heap holds, and explains why one distance per node would lose valid paths. A Staff-level answer also names the alternatives, limited Bellman-Ford and layered BFS, and gives the cost of the expanded graph.

The consequence of getting this wrong is concrete: the code passes the sample cases and returns a wrong answer, or no answer at all, on the cases that matter. The sections below show one such case with real numbers.

Dijkstra with state from first principles

Dijkstra with state

Dijkstra with state is a shortest-path method that runs Dijkstra's algorithm on an expanded graph whose nodes are pairs such as (city, flights used), so that a limit on stops, fuel or discounts becomes part of the node and the heap enforces it without a special case.

Stale entry

A stale entry is a heap entry whose cost is higher than the best distance already recorded for its state, left behind because a heap cannot delete from the middle, and the loop skips it when it is popped instead of expanding it again.

In plain words

Imagine a bus pass that allows a fixed number of rides. Arriving in a town with three rides left and arriving with none left are different situations, even though the town is the same. Treat each pair of town and rides used as its own "copy" of the town. The cheapest route to the destination is the cheapest arrival at any copy of it.

The analogy breaks in one place. The copies are not separate places on the map. They exist only inside the algorithm. The answer is the minimum over the copies of the target.

In one precise sentence: Dijkstra with state runs the ordinary algorithm on an expanded graph, a graph whose nodes are the states, and lets each edge move you from one state to the next. It is one of three approaches the lecture lists for the "at most K stops" variant, next to limited Bellman-Ford and layered BFS (Illinois lecture notes, October 2025).

Step 1: Choose what the state remembers

The state holds exactly what the constraint needs and nothing more. The state is a pair of node and flights used. Other problems use other pairs: practitioner templates list stops used, fuel left and discounts used (coderraj07, Medium).

For the flights problem the limit is on stops, but a stop is an intermediate city, so at most k stops means at most k plus one flights. The problem's own example with k equal to zero returns the direct flight, price 500 (LeetCode). Count flights in the state and the off-by-one disappears: the limit is k plus one flights.

You now know what a node of the expanded graph is. Next comes the table that stores one distance for each such node.

Step 2: Keep one distance per state, not per node

Plain Dijkstra keeps one distance per node and finalises a node when it is popped, which is correct only because edge costs are not negative (Wikipedia; Dijkstra, 1959). Plain Dijkstra has no notion of the stop limit (Feresini, Medium), so the limit must be carried by the table: dist[node][flights_used], the cheapest known cost to reach that node using exactly that many flights.

Why not one number per node? The cheapest arrival at a node may use too many flights, while a costlier arrival with fewer flights is the one that can still reach the target. On the illustrative graph of the worked example, node 2 is first reached for cost 5 in one flight and later for cost 2 in two flights. With one distance per node the cost-5 entry is discarded, and the search returns -1 where the right answer is 6.¹

The stale-entry check follows the same rule: compare the popped cost with dist[node][flights_used], never with a per-node value.

Step 3: Expand only while the limit allows

The heap holds entries of the form (cost, node, flights used). The heap orders entries by cost. Pop the cheapest entry; if it already uses the maximum number of flights, do not expand it. Otherwise relax every outgoing edge into the next layer, flights used plus one, and push an entry only if the new cost beats the stored distance of that state.

import heapq
from collections import defaultdict

def cheapest(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    max_flights = k + 1
    INF = float("inf")
    dist = [[INF] * (max_flights + 1) for _ in range(n)]
    dist[src][0] = 0
    heap = [(0, src, 0)]
    while heap:
        cost, node, used = heapq.heappop(heap)
        if node == dst:
            return cost
        if cost > dist[node][used] or used == max_flights:
            continue
        for nxt, price in graph[node]:
            new_cost = cost + price
            if new_cost < dist[nxt][used + 1]:
                dist[nxt][used + 1] = new_cost
                heapq.heappush(heap, (new_cost, nxt, used + 1))
    return -1

The adjacency list uses a defaultdict, a Python dictionary that creates missing keys on demand. In the loop, the line with continue is both the stale-entry check and the limit check, and it stops expansion of that entry, not the search.

Step 4: Stop when the target is popped

Dijkstra can stop as soon as the shortest path to a specific destination is known (Wikipedia; Dijkstra, 1959). Here that means returning at the first pop of the target. Because the heap pops in cost order, the first pop of the target is the answer. If the heap empties first, no route fits the limit, and the function returns -1.

This early return depends on ordering entries by cost. If you order the heap by flights used instead, the first pop of the target is no longer the cheapest, so keep cost first in the tuple.

The cost of the search follows from the size of the expanded graph. Here V is the number of nodes and E the number of edges. A heap-based Dijkstra runs in $O((V+E)\log V)$ (see the running-time section of Wikipedia and the Illinois lecture). The expanded graph has $V(K+2)$ states and about $E(K+1)$ transitions, so the bound becomes about $O((K+1)(V+E)\log ((K+1)V))$; this bound is derived here, not quoted from a source.¹

1 · State2 · Distances3 · Heap4 · StopReplay

Step-by-step description

1. The state is node plus flights used.
2. One distance per state, not per node.
3. Pop by cost, expand while flights remain.
4. The first pop of the target is the answer.

• The state is a pair of node and flights used.
• The heap orders entries by cost, and the first pop of the target is the answer.

Worked example

The first input is Example 1 of the LeetCode problem: four cities, flights 0 to 1 for 100, 1 to 2 for 100, 2 to 0 for 100, 1 to 3 for 600 and 2 to 3 for 200, from city 0 to city 3 with k equal to 1. Plain Dijkstra ignores the limit and returns 400 along 0, 1, 2, 3, which uses three flights and breaks the limit.¹ With state, the answer is 700 along 0, 1, 3.¹

The heap trace is short. Pop (0, city 0, 0 flights) and push (100, city 1, 1). Pop that and push (200, city 2, 2) and (700, city 3, 2). Pop (200, city 2, 2): two flights is the maximum, so it is not expanded. Pop (700, city 3, 2): the target, so return 700. That is 4 pops in total.¹

Examples 2 and 3 of the same page share one graph: flights 0 to 1 for 100, 1 to 2 for 100 and 0 to 2 for 500. With k equal to 1 the answer is 200, and with k equal to 0 it is 500.¹

The second input is an illustrative graph built to show the trap: flights 0 to 1 for 1, 1 to 2 for 1, 0 to 2 for 5 and 2 to 3 for 1, from city 0 to city 3 with k equal to 1. The correct answer is 6 along 0, 2, 3. A version with one distance per node returns -1, because it records node 2 at cost 2 with two flights and then drops the cost-5 entry that still had a flight left.¹

The constraints on the problem page allow up to 100 cities and no more than n(n-1)/2 flights (LeetCode). With 100 nodes, 4,950 edges and K equal to 99, the expanded graph has at most 10,100 states and 495,000 transitions.¹ With 100 nodes the expanded graph has 200 states at K equal to 0 and 10,100 states at K equal to 99.¹

Text description of the diagram

• With 100 nodes the expanded graph has 200 states at K equal to 0 and 10,100 states at K equal to 99.
• The expanded graph grows in step with the stop limit K, so a small K keeps the search small.

Trade-offs and edge cases

Dijkstra with state is not the only route. The lecture lists three approaches for the "at most K stops" variant: Bellman-Ford limited to K+1 rounds, layered BFS, and Dijkstra on an expanded state space (Illinois lecture).

Limited Bellman-Ford relaxes every edge in each of K+1 rounds and needs no heap. It runs in $O((K+1)E)$ time and O(V) space, with no log factor; this bound is derived here, not quoted from a source. On the largest case in the constraints that is 4,950 edges times 100 rounds, or 495,000 relaxations, so asymptotically it is no worse than the heap version.¹ Its drawback is that every round runs, with no early exit, while Dijkstra with state pays a log factor but can stop at the first pop of the target.

Bellman-Ford has one classic bug. Each round must relax from a copy of the previous round's distances (tmp = dist[:]); updating in place lets one round chain several edges and break the limit. A Staff-level refinement for the heap version is dominance pruning: skip a state when the same node was already reached with fewer flights at a lower or equal cost, because that earlier state can do everything the later one can.

Text description of the diagram

• Bellman-Ford limited to K+1 rounds is an alternative to the heap.
• Layered BFS with cost pruning is another alternative.

Edge cases to name aloud:

• Negative edges. Dijkstra needs non-negative edge costs, because a node is finalised when popped (Wikipedia). Adding state does not repair that. A graph with negative edges calls for Bellman-Ford.
• Equal weights. When every edge costs the same, BFS runs in O(V + E) (Illinois lecture) and a heap is unnecessary. When edge costs are only 0 or 1, a double-ended queue gives 0-1 BFS.
• Unreachable targets. If no route fits inside the limit, return the agreed sentinel, usually -1.
• State blow-up. Each extra dimension multiplies the state count. A state of (node, flights used, discounts used) is fine for small limits and poor for large ones.

For another graph pattern that works on a prepared structure, see topological sort; Python-specific habits for the code above are in Python interview questions.

How to answer it in an interview

The spoken structure: say why plain Dijkstra fails, name the state, say what the table and the heap hold, state when you stop, then give the cost.

Common mistakes

• "I keep one dist[city] and add a stops counter to the heap." (wrong) The counter never reaches the table, so a cheap arrival with too many flights hides the valid one. (right) "The distance table is indexed by city and flights used."
• "At most k stops means k edges." (wrong) The problem's own k = 0 example returns the direct flight, one edge. (right) "At most k stops means at most k plus one flights."
• "Skip a popped entry if its cost is above dist[city]." (wrong) That compares against the wrong table. (right) "Compare against dist[city][flights_used]."
• "Dijkstra works with negative prices if I add state." (wrong) A node is finalised on pop, which needs non-negative costs. (right) "With negative edges I switch to Bellman-Ford."
• "Order the heap by flights used so the limit is checked first." (wrong) The first pop of the target is then not the cheapest. (right) "Order by cost; the limit is checked on expansion."
• "In Bellman-Ford I update dist in place as I loop over the edges." (wrong) One round can then chain several edges and break the limit. (right) "Each round relaxes from a copy of the previous round's distances."

Follow-up questions

How do you solve Cheapest Flights Within K Stops with Dijkstra?

Make the state (city, flights used), allow at most k plus one flights, keep dist[city][flights_used], run a cost-ordered heap and return the first pop of the destination. Step 3 above gives the full function, including the stale-entry check.

What is the time complexity of Dijkstra with state?

It is about $O((K+1)(V+E)\log ((K+1)V))$, where V is the number of nodes and E the number of edges: the usual $O((V+E)\log V)$ heap bound applied to an expanded graph with $V(K+2)$ states and about $E(K+1)$ transitions (the expanded form is derived in Step 4). Space is the size of the state table.

Why is a single distance per node wrong when there is a stop limit?

The cheapest known arrival at a node can use too many flights and then blocks costlier arrivals that still have flights left. On the illustrative trap graph this turns the correct 6 into -1.¹

Does k stops mean k edges?

No. A stop is an intermediate city, so k stops means at most k plus one flights; the problem's k = 0 example returns the direct flight (LeetCode).

When should you use Bellman-Ford instead of Dijkstra with state?

Limited Bellman-Ford costs $O((K+1)E)$ with no log factor but has no early exit, and it also tolerates negative edge costs. Dijkstra with state carries a log factor but can stop at the first pop of the target, provided all costs are non-negative. More pattern practice is in the coding interview guide.

Sources

1. Cheapest Flights Within K Stops - LeetCode — LeetCode, 26 Oct 2026
2. ECE374-B Lecture 16, Shortest paths I: BFS and Dijkstra — University of Illinois Urbana-Champaign (course archive), 23 Oct 2025
3. Dijkstra's algorithm — Wikipedia, 26 Oct 2026
4. A note on two problems in connexion with graphs (Numerische Mathematik 1, 269-271) — Springer (E. W. Dijkstra), 1 Dec 1959
5. Constrained shortest path algorithms: Cheapest Flights Within K Stops — Medium (F. Feresini), 26 Oct 2026
6. Dijkstra's Algorithm: Templates and Problem Solving — Medium (coderraj07), 26 Oct 2026