Dijkstra's algorithm

Problem

You have a graph whose edges carry costs (travel time, price, effort) and a start node. The question is the cheapest way to reach one node or all of them. Breadth-first search finds fewest edges, not least cost, and trying every path is exponential. The costs are never negative, which is the property that makes a greedy choice safe.

Intuition

Imagine lighting a fuse at the start node. The fire runs along every edge at a speed set by its cost, and the order in which nodes catch fire is the order of their shortest distance. Dijkstra simulates exactly that. At any moment the node that will catch fire next is the cheapest one among those reachable from nodes already burning, and a heap hands you that node in O(log n).

Why can the first pop be trusted? Suppose node u is the cheapest frontier node with distance d. Any other route to u would have to leave the burning region through some other frontier node whose distance is already at least d, and then pay a cost that is not negative, so it arrives at u no earlier than d. That argument is the whole proof, and it is exactly where a negative edge breaks it.

Edge labels are costs and every edge is directed from the first node listed to the second (away from node 0, except 2 → 1); thick edges form the cheapest route to node 5. The diagram scrolls sideways on a narrow screen.

Mechanics

The loop

Keep dist, the final distance of each settled node, and a heap of (distance, node) pairs. Push the start with distance 0. Repeatedly pop the smallest pair. If its node is already settled, skip it. Otherwise record its distance, and for each outgoing edge push (distance + cost, neighbor) when that beats the best known distance to the neighbor.

Stale entries

Python's heap has no decrease-key. Instead, whenever a better route is found, push another entry and leave the old one in the heap. When the old entry is eventually popped the node is already settled, and the pop is skipped. This costs at most one push per edge, so the heap holds at most E entries and each push or pop is O(log E) = O(log V).

Invariant and proof

Every time a node is popped and not skipped, its distance is final, and the settled distances come out in non-decreasing order. Induction: assume it holds for all settled nodes so far. The popped pair is the smallest in the heap, and any unsettled node's true shortest route must cross from the settled set to the unsettled set by one edge, so its true distance is at least the smallest heap entry. Non-negative edges never reduce a distance, which is the step a negative edge violates.

Early exit and variants

If you only need one target, stop when it is first popped; its distance is final then. The cost need not be a sum: any combination cost(path + edge) that never decreases as the path grows works, such as the maximum step on the path, or the maximum cell value seen.

The bars only ever grow: that monotone order is the invariant in action.

Worked example

On the graph above, starting from node 0, the nodes settle in this order with these distances: node 0 at 0; node 2 at 1; node 1 at 3; node 3 at 4; node 4 at 7; node 5 at 8. The final distance array is 0, 3, 1, 4, 7, 8. The cheapest route to node 5 is 0 → 2 → 1 → 3 → 4 → 5, costing 8. Note that the direct edge 0 → 1 costs 4, but going through node 2 costs only 3, so node 1 is pushed twice: the cost-4 entry goes stale.

Network delay. With travel times 2→1 (1), 2→3 (1), 3→4 (1) and a signal sent from node 2 on 4 nodes, the last node to hear is node 4 after 2. Unreachable nodes make the answer -1: with only the edge 1→2 and 3 nodes, a signal from node 1 never reaches node 3, so the answer is -1.

Minimum effort. On the height grid [[1, 2, 2], [3, 8, 2], [5, 3, 5]] the best route's biggest height jump is 2. Rising water. On [[0, 2], [1, 3]] you can reach the far corner at time 3, because the final cell only opens then.

Why negative edges break it. Take edges 0→1 (1), 0→2 (2) and 2→1 (-5). Dijkstra settles node 1 at distance 1 first, but the true shortest distance is -3, via node 2. The settled value can no longer be improved, so the answer is wrong.

Implementation

import heapq

def dijkstra(graph, source):
    # graph[u] is a list of (v, cost) with cost >= 0
    dist = {}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue
        dist[u] = d
        for v, cost in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + cost, v))
    return dist


def network_delay_time(times, n, k):
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))
    dist = dijkstra(graph, k)
    return max(dist.values()) if len(dist) == n else -1

Variations and edge cases

def minimum_effort(heights):
    rows, cols = len(heights), len(heights[0])
    best = {(0, 0): 0}
    heap = [(0, 0, 0)]
    while heap:
        effort, r, c = heapq.heappop(heap)
        if (r, c) == (rows - 1, cols - 1):
            return effort
        if effort > best[(r, c)]:
            continue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                step = max(effort, abs(heights[nr][nc] - heights[r][c]))
                if step < best.get((nr, nc), float("inf")):
                    best[(nr, nc)] = step
                    heapq.heappush(heap, (step, nr, nc))


def swim_in_water(grid):
    n = len(grid)
    seen = {(0, 0)}
    heap = [(grid[0][0], 0, 0)]
    while heap:
        t, r, c = heapq.heappop(heap)
        if (r, c) == (n - 1, n - 1):
            return t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))

• Skip stale entries. Without the settled check the algorithm still works but may reprocess nodes and can blow up on dense graphs.
• Heap ties. Tuples compare by distance first, then node. Use integer node ids, or add a counter, if nodes are not comparable.
• Unreachable nodes. They never appear in dist; check the count before taking a maximum.
• Directed vs. undirected. For an undirected graph add each edge in both directions.
• Zero-cost edges are fine. A negative edge is not: use Bellman-Ford.
• Reconstructing the route. Store the parent whenever you push a better distance, then walk parents back from the target.
• Edge cases: source equals target (distance 0), a single node, parallel edges (the heap picks the cheaper), and disconnected graphs.

Complexity and tradeoffs

• Time: O((V + E) log V) with a binary heap, since each edge causes at most one push and each push or pop costs O(log V).
• Space: O(V + E) for the graph, plus O(E) heap entries in the worst case.
• Baseline. Trying every simple path is exponential. Bellman-Ford handles any weights in O(V · E), slower but more general. A dense graph can use an array scan instead of a heap for O(V²).
• Versus BFS. With uniform costs BFS is O(V + E) and simpler; the heap only earns its log factor when costs differ.
• When it fails. Negative edges (use Bellman-Ford), paths limited to k edges (Bellman-Ford rounds, or a state of node plus stops), and all-pairs distances (run it from each node, or use Floyd-Warshall).

Problems

Network Delay Time is the textbook run: distances from one source, answered by the largest. Swim in Rising Water and Path With Minimum Effort keep the same loop but change the cost into a running maximum. Cheapest Flights Within K Stops, homed on the Bellman-Ford page, adds a stop limit that plain Dijkstra cannot enforce.

Medium

• 743. Network Delay Time NeetCode 150 NeetCode 250
  Run Dijkstra from the source; the answer is the largest final distance, or -1 if some node is never reached.
• 1631. Path With Minimum Effort NeetCode 250
  A path's effort is its largest single step, so run Dijkstra where a path's cost is its maximum step instead of a sum.

Hard

• 778. Swim in Rising Water NeetCode 150 NeetCode 250
  Treat a path's cost as its highest cell, and Dijkstra with that max rule finds the lowest possible maximum.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 787. Cheapest Flights Within K Stops Medium

Connections

Dijkstra is BFS with a priority queue instead of a plain queue, and it leans on the heap page for its inner loop. Minimizing a maximum along a path can also be solved by binary searching the answer or by adding edges in cost order with union-find, which is why those pages are linked.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 22.3 (Dijkstra's algorithm, with the correctness proof).
• Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik 1, 1959, the original paper.
• Sedgewick and Wayne, Algorithms, section 4.4 (shortest paths).
• Skiena, The Algorithm Design Manual, section on shortest paths.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.