Dijkstra's Shortest Paths

Breadth-first search finds the route with the fewest hops. That is the right answer only when every hop costs the same. In practice they never do: routing an order across venues, each leg has its own fee, its own expected slippage and its own latency. Two hops through a cheap venue can easily beat one hop through an expensive one. When edges carry different weights, "fewest edges" and "cheapest total" are different questions, and Dijkstra's algorithm answers the second.

The setup: a graph where each edge has a non-negative cost, and one starting node. Dijkstra produces the minimum total cost from that start to every other node, plus the route that achieves it.

The idea: always expand the cheapest frontier node

Keep a tentative distance for every node — zero for the start, infinity for everything else — and a priority queue of nodes ordered by that tentative distance. Repeatedly pull out the cheapest unfinalised node, and for each of its neighbours check whether going through it is an improvement. That check is called relaxation:

$$\text{dist}[v] \leftarrow \min\big(\text{dist}[v],\ \text{dist}[u] + w(u,v)\big)$$

In words: the best known cost to reach $v$ is either what you already had, or the cost of reaching $u$ plus the price of the edge from $u$ to $v$ — whichever is smaller.

The reason this greedy rule is correct is worth saying out loud, because interviewers ask. When you pop the node with the smallest tentative distance, no cheaper route to it can still be discovered: any such route would have to pass through some other unfinalised node, which by construction already costs at least as much, and adding more non-negative edges cannot make it cheaper. So the moment a node is popped, its distance is final. That argument uses non-negativity twice, which is exactly why negative edges break the algorithm.

With a binary heap the cost is

$$O\big((V + E)\log V\big),$$

because each of the $E$ edges can push one entry onto a heap of size at most $V$, and each push or pop costs $\log V$. A Fibonacci heap improves this to $O(E + V\log V)$ in theory; nobody uses one in practice.

Worked example: trace it on that graph

Edges: A–B 4, A–C 2, C–B 1, B–D 5, C–D 8, C–E 10, D–E 2. Start at A.

1. dist = {A:0, rest:∞}. Pop A (0). Relax: B = 4, C = 2.
2. Pop C (2, the cheapest in the queue, not B). Relax: B = min(4, 2+1) = 3 — improved; D = 2+8 = 10; E = 2+10 = 12.
3. Pop B (3). Relax: D = min(10, 3+5) = 8 — improved.
4. Pop D (8). Relax: E = min(12, 8+2) = 10 — improved.
5. Pop E (10). Nothing left to improve. Done.

Answer: A→E costs 10 via A→C→B→D→E. Note two things. B was first set to 4 and later lowered to 3, so a tentative distance is genuinely tentative until its node is popped. And the direct edge C→E at 10 lost to a three-edge route costing 8 more from a cheaper base — greedy on total cost, never on hop count.

import heapq

def dijkstra(graph, src):              # O((V + E) log V)
    dist = {v: float("inf") for v in graph}
    dist[src] = 0
    pq = [(0, src)]                    # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:                # stale duplicate, skip it
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))   # lazy: push, never decrease-key
    return dist

Where it shows up

Interview versions: network delay time, path with minimum effort, cheapest flights within k stops (needs a modification — the state is (node, stops), not just node), and swimming-in-rising-water. Expect follow-ups on why non-negativity matters and how you would reconstruct the path.

On a desk, Smart Order Routing is a shortest-path problem where the "distance" is total expected cost: exchange fees and rebates, expected slippage, and the latency penalty of each leg. Cross-currency execution paths through intermediate legs are the same computation. Colocation and network teams route market-data feeds by measured latency rather than hop count, which is Dijkstra with microseconds as weights. And the collateral-transformation problem — cheapest sequence of swaps that turns what you hold into what you must post — is a weighted shortest path over an instrument graph.