Dijkstra's Algorithm

The Data Structures course defined graphs and established breadth-first and depth-first search. Breadth-first search found the shortest path in terms of edge count: every edge was counted as equally costly.

In real problems, edges carry different costs — distance, time, fare. This topic builds algorithms that work on weighted graphs, and its first question is the shortest path.

Problem and Notation

Single-source shortest path problem: Given a weighted graph and a source vertex, find the paths of lowest total weight from the source to every other vertex.

The same graph is used throughout this topic: vertices A–F, edges directed and weighted.

graph: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 5), ("D", 10)],
    "C": [("E", 3)],
    "D": [("F", 11)],
    "E": [("D", 4)],
    "F": [],
}

The adjacency list representation suits sparse graphs, and traversing all edges is $O(V + E)$. In dense graphs the adjacency matrix is preferred; the cost impact of this choice was covered in the Data Structures course.

Relaxation

The common building block of these algorithms is relaxation: lowering a known estimate using a better path that has been found.

For each vertex, the best known distance from the source is kept as u[v]; initially $0$ for the source and infinity for the rest. For an edge (v, w):

$$u[w] > u[v] + \text{weight}(v, w) \implies u[w] \leftarrow u[v] + \text{weight}(v, w)$$

Relaxation never produces an incorrect value: u[w] is always the length of a path that actually exists. Algorithms differ in the guarantee they give about when these values become final.

The Greedy Choice

Dijkstra’s algorithm rests on this idea: among vertices not yet settled, the one with the smallest estimate is now settled.

The justification rests on weights being non-negative. Any other path from the source to v must pass through an unsettled vertex; since that vertex’s estimate is not smaller than u[v], and the remaining edges cannot reduce the cost, the alternative path cannot be shorter.

This reasoning gives the algorithm’s invariant: the distances of settled vertices are the true shortest-path lengths.

Implementation

import heapq


def dijkstra(graph: dict[str, list[tuple[str, int]]],
             source: str) -> tuple[dict[str, float], dict[str, str | None]]:
    """Returns (distances, previous vertices). Weights must not be negative."""
    distance: dict[str, float] = {vertex: float("inf") for vertex in graph}
    previous: dict[str, str | None] = {vertex: None for vertex in graph}
    distance[source] = 0
    queue: list[tuple[float, str]] = [(0, source)]
    settled: set[str] = set()

    while queue:
        dist, v = heapq.heappop(queue)
        if v in settled:               # stale entry: skip
            continue
        settled.add(v)
        for neighbor, weight in graph[v]:
            if dist + weight < distance[neighbor]:
                distance[neighbor] = dist + weight
                previous[neighbor] = v
                heapq.heappush(queue, (distance[neighbor], neighbor))
    return distance, previous


distance, previous = dijkstra(graph, "A")
print(distance)
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

The direct route from A to D via A→B→D has length 14; the algorithm finds the A→C→E→D path with length 9. The greedy choice does not prevent a start that looks longer from summing to less — because the choice looks at accumulated distances, not at individual edges.

Reconstructing the Path

Distance alone is not enough; which path was taken is also needed. The previous dictionary carries this information: each vertex points to the vertex it was reached from on the shortest path.

def build_path(previous: dict[str, str | None], target: str) -> list[str]:
    path: list[str] = []
    vertex: str | None = target
    while vertex is not None:
        path.append(vertex)
        vertex = previous[vertex]
    return path[::-1]


print(build_path(previous, "F"))       # ['A', 'C', 'E', 'D', 'F']
print(build_path(previous, "B"))       # ['A', 'B']

These pointers form a shortest path tree: a tree rooted at the source that jointly encodes the shortest paths to every vertex.

Cost

Every vertex is settled at most once; every edge produces at most one relaxation and one queue insertion. With a binary heap:

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

The queue can hold multiple entries for the same vertex — the implementation here skips stale entries as they are popped. This lazy deletion gives the same asymptotic bound without requiring a priority queue with a decrease-key operation, and it shortens the code noticeably.

In dense graphs ($E \approx V^2$), a variant that scans an array instead of using a queue is $O(V^2)$ and can be faster. A theoretical variant using a Fibonacci heap gives $O(E + V \log V)$; its constants are large, so it is rarely seen in practice.

Common Variants

The basic structure adapts to different questions with small changes.

Early exit for a single target. If only the distance to a specific vertex is needed, the search can stop the moment that vertex is popped from the queue; its value is settled at that point. The remaining vertices are never processed.

Multi-source search. For questions like “distance to the nearest warehouse,” all sources are placed in the queue with zero distance at the start. This is equivalent to a graph where a single artificial source draws a zero-weight edge to every warehouse; it is the weighted counterpart of the multi-source breadth-first search from the Data Structures course.

Unreachable vertices. The distance of a vertex unreachable from the source stays infinite. Code that uses the result must test for this value; treating infinity as an ordinary numeric distance leads to silent errors.

Weights restricted to 0 and 1. In this case a double-ended queue suffices instead of a priority queue: a zero-weight edge is added to the front, a one-weight edge to the back. The cost drops to $O(V + E)$ — the logarithmic factor is the price of weight variety.

The Non-Negative Weight Restriction

The algorithm’s correctness rested on the assumption that “a settled vertex’s value can never drop again.” A negative-weight edge breaks this assumption.

with_negative_weight = {
    "A": [("B", 1), ("C", 2)],
    "B": [("D", 1)],
    "C": [("B", -2)],
    "D": [],
}

print(dijkstra(with_negative_weight, "A")[0])
# {'A': 0, 'B': 0, 'C': 2, 'D': 2}      — D wrong: the true distance is 1

Vertex B is settled via the direct edge of weight 1, and D is relaxed to 2 through it. Then C is processed, and it turns out the A→C→B path is $2 + (-2) = 0$; B’s value is corrected, but since B is already counted as settled, its outgoing edges are never relaxed again. D stays at its old value.

The algorithm raises no error; it silently produces the wrong result. This is one of the examples showing why documenting preconditions is not a formality.

An algorithm that works with negative weights is the subject of the next lesson.

Summary

• The single-source shortest path problem asks for the lowest total-cost paths from the source to every vertex in a weighted graph.
• Relaxation lowers a vertex’s estimated distance using a better path that has been found, and every estimate corresponds to a real path.
• Dijkstra’s algorithm picks the smallest estimate among unsettled vertices; its correctness rests on weights being non-negative.
• The priority-queue implementation is $O((V + E)\log V)$; lazy deletion avoids needing a decrease-key operation.
• Previous-vertex pointers encode the shortest path tree and allow the path to be reconstructed.
• Under negative weight, the algorithm produces the wrong result without raising an error.

Next Step

Negative weights arise in real problems: gain in currency conversion cycles, recovery in a production plan. The next lesson builds the Bellman–Ford algorithm, which abandons the greedy choice and relaxes every edge repeatedly, and shows why negative cycles make the problem undefined.