Dijkstra's Algorithm, in depth: a reusable engine for state graphs, custom path costs, time-dependent edges and certified answers

The engine: one loop, a pluggable expansion

Strip Dijkstra's algorithm to its skeleton and it has only three moving parts. There is a set of start states with a starting label. There is a rule that, given a settled state and its label, produces candidate labels for neighbouring states. And there is a priority queue that always hands back the unsettled state with the best label so far. Nothing in that description says the states are road intersections or that labels are sums of integers.

The engine below makes that explicit. The caller supplies expand(u, d), which yields each neighbour together with the label it would get by arriving from u with label d. For ordinary graphs that label is d + w. Everything else in this article is a different expand function; the loop never changes.

import heapq
from itertools import count

def dijkstra(sources, expand, is_target=None, zero=0):
    """sources: start states. expand(u, d) yields (v, label_of_v_via_u).
    Labels only need to be comparable; see the two conditions below."""
    dist, parent, done = {}, {}, set()
    tie = count()                      # states themselves are never compared
    heap = []
    for s in sources:
        dist[s], parent[s] = zero, None
        heapq.heappush(heap, (zero, next(tie), s))
    while heap:
        d, _, u = heapq.heappop(heap)
        if u in done:
            continue                   # stale entry left by lazy deletion
        done.add(u)                    # d is final for u
        if is_target is not None and is_target(u):
            return u, dist, parent     # stop on POP, never on push
        for v, nd in expand(u, d):
            if v not in done and (v not in dist or nd < dist[v]):
                dist[v], parent[v] = nd, u
                heapq.heappush(heap, (nd, next(tie), v))
    return None, dist, parent

def path_to(parent, t):
    out = []
    while t is not None:
        out.append(t)
        t = parent[t]
    return out[::-1]

Three details are deliberate. A counter breaks heap ties, so states are never compared directly. The graph is implicit: states exist only once reached, which matters when the state space is a product of several dimensions. And the target test is a predicate, so the caller can say "any state at node T".

The two conditions any cost model must meet

The proof that a popped label is final rests on one step: any other route to u leaves the settled region through a frontier state whose label is already no better, and continuing along it cannot improve it. Two properties make that step valid.

• Monotone: extending a path never makes its label better. For sums this is exactly the rule that weights are non-negative; in general it means the label expand produces is never smaller than d.
• Isotone: extending two paths by the same edge preserves their order. If label a is no worse than label b at state u, then a extended along an edge is no worse than b extended along that edge. This is what lets the algorithm discard the worse label at u without losing any future route.

When either condition fails, the output can be wrong without any error. The table lists common cost models and whether they qualify as they stand.

State graphs: when the node is not enough

The last row of the table is the most useful trick here. If the next step's cost depends on the path so far, such as coupons left, fuel remaining or the current transit line, the node alone is not a sufficient state. Two routes reaching one intersection with different fuel are not interchangeable.

The fix is to make the state a tuple of the node and whatever history matters. Each node becomes one state per value of the extra dimension, edges connect states where the move is legal, the cost is again a plain non-negative sum, and the unmodified engine is correct.

Consider a network with nodes S, A, B and T, edges S to A of weight 4, S to B of weight 7, A to T of weight 10 and B to T of weight 6, and one voucher that makes any single edge free. The product graph has two layers, one where the voucher is unused and one where it is spent. Each road edge appears in both layers with its weight, and also as a zero-cost edge from the unused layer down to the spent layer.

GRAPH = {"S": [("A", 4), ("B", 7)], "A": [("T", 10)], "B": [("T", 6)], "T": []}
K = 1                                   # free edges allowed

def coupon_expand(state, d):
    node, used = state
    for nxt, w in GRAPH[node]:
        yield (nxt, used), d + w        # pay for the edge
        if used < K:
            yield (nxt, used + 1), d    # spend a coupon on it

t, dist, parent = dijkstra([("S", 0)], coupon_expand, is_target=lambda s: s[0] == "T")
print(dist[t], path_to(parent, t))      # 4 [('S', 0), ('A', 0), ('T', 1)]

Worked example: tracing the free-edge search

Tracing the search by hand shows why the layered graph is needed. Each row is one pop from the heap, in order, and the right-hand column shows the labels that pop improved.

The answer is 4: pay for S to A and ride A to T for free. Without the voucher, the best route is S, B, T at 13. A single-layer search that keeps one label per node plus a "voucher used" flag gets this wrong. It reaches A for 0 by spending the voucher on S to A, which beats 4, so it keeps that label and forgets that A was also reachable for 4 with the voucher unspent. It reaches B for 0 the same way and returns 6 through B. The route that saves the voucher for the expensive edge was discarded. Keeping (A,0) and (A,1) as separate states is what preserves it.

The stopping rule also matters. Stopping at pop 3, when (T,1) first received a label, would have returned 6. The first time any T state is popped, its label is final, and because the target predicate accepts every layer, the first T pop is the best answer over all voucher counts.

Custom costs in code

Each cost model in the table is only an expand function and a starting label. For widest path, negating the bottleneck lets the same min-heap work. Reliability multiplies probabilities; negative logarithms turn the product into a sum of non-negative terms. Lexicographic labels state a tie-break policy exactly instead of leaving it to heap order.

import math

# Widest path: maximise the smallest capacity on the route.
# Label = -bottleneck, so "smaller is better" still holds for the min-heap.
def widest_expand(u, d):
    for v, cap in CAPS[u]:
        yield v, max(d, -cap)           # bottleneck can only shrink
# call with zero=-math.inf

# Most reliable path: maximise the product of success probabilities.
def reliable_expand(u, d):
    for v, p in PROB[u]:                # 0 < p <= 1
        yield v, d - math.log(p)        # each term is >= 0

# Fewest hops among the cheapest routes: lexicographic tuples.
def lex_expand(u, d):
    cost, hops = d
    for v, w in GRAPH[u]:
        yield v, (cost + w, hops + 1)
# call with zero=(0, 0); Python compares tuples left to right

Floating-point logarithms are not exact, so equally reliable routes can compare unequal; test with a tolerance.

Time-dependent edges and the FIFO rule

In a timetabled network an edge's cost depends on when you reach it: a bus every 15 minutes costs a short wait or a long one. The label becomes the arrival time, and expand asks each edge for the earliest arrival at its far end: the current time plus walking time, or the next departure plus ride time.

The condition that makes this safe is known as FIFO, first in, first out: arriving at an edge later never lets you reach its far end earlier. Walking satisfies it trivially, and so does any timetable where waiting for a later departure is allowed, because the earlier traveller can always wait for the same vehicle. FIFO is exactly the isotone property for time labels. When the network is FIFO, the engine computes earliest arrival times correctly with no changes.

FIFO breaks when waiting is forbidden, or when a later express overtakes an earlier stopping train the traveller cannot leave. A worse label can then lead to a better arrival, and the search discards it. Repair it by allowing waiting, or by putting the vehicle into the state.

Certifying the answer

A shortest-path result can be checked far more cheaply than it can be computed. A complete run is correct if every source has the zero label, no edge produces a better label than the one already stored at its head, and every non-source state's recorded parent edge produces exactly the stored label. The first two conditions show no route is better than the stored one; the third shows a route achieving it exists.

def certify(sources, expand, dist, parent, zero=0):
    """Checks a COMPLETE run (no early exit). O(V + E) versus O((V + E) log V)."""
    for s in sources:
        assert dist[s] == zero and parent[s] is None
    for u, du in dist.items():
        for v, nd in expand(u, du):
            assert v in dist and dist[v] <= nd, f"edge {u}->{v} improves {v}"
        p = parent[u]
        if p is not None:
            assert any(v == u and nd == du for v, nd in expand(p, dist[p])), \
                f"parent edge of {u} does not produce its label"

Run it in property-based tests on random small graphs, and in production behind a sampling flag when results feed billing or routing. It tests the output without trusting the code that produced it. It needs a complete search, because an early exit leaves labels that are not final.

Performance of state expansion

Adding a dimension multiplies the graph. With K vouchers there are V(K + 1) states and up to 2E(K + 1) edges, so the running time with a binary heap grows by roughly a factor of K + 1. For small K that is the right trade. For large or continuous dimensions such as battery charge, discretise the dimension or keep only non-dominated labels per node: a label with no more cost and at least as much remaining resource makes the other redundant. That is the label-setting method used for resource-constrained shortest paths.

Tuple-keyed dictionaries are convenient and slow. In a hot path, encode each state as an integer such as node * (K + 1) + used and keep labels in flat arrays, with a heap like the one in the heap operations guide.

Failure modes

• Folding history into a flag. Tracking a voucher or fuel level as data on the node instead of as part of the state silently discards routes, as the trace showed.
• Comparing states in the heap. Pushing (label, state) pairs crashes when states are dictionaries and gives arbitrary tie-breaks otherwise. Use a counter or an explicit tie-break field.
• A cost model that is not isotone. Discounts that depend on history, penalties that depend on the arrival label, or non-FIFO timetables produce wrong answers with no error.
• Exploding state spaces. Three extra dimensions of ten values each multiply the graph a thousandfold. Measure the product size before committing to the design.

What to do next

1. Implement the engine with expand(u, d) and run the free-edge example until it prints 4 and the path through A.
2. For each cost model you use, write down the label, the extension and a one-line argument that it is monotone and isotone.
3. Move any path-dependent quantity into the state and compute the product graph's size before building it.
4. Add the certificate check to your tests and run it on random graphs against a brute-force search for small sizes.
5. Replace tuple-keyed dictionaries with integer-encoded states and arrays once the design is fixed, then profile.
6. Revisit BFS for unit weights and the greedy method for why the settle step works.