Dijkstra's Algorithm

Phase 1f(x)

The Mathematics

Greedy relaxation, priority queue, and shortest-path optimality

Problem Definition

Given a weighted directed graph $G = (V, E)$ with non-negative edge weights $w(u, v) \geq 0$ and a source vertex $s$ , find the shortest path distance from $s$ to every other vertex:

\text{dist}(s, v) = \min \sum_{(u_i, u_{i+1}) \in P} w(u_i, u_{i+1})

Relaxation

The key operation: if we find a shorter path to $u$ via $v$ , update the estimate:

\text{if } \text{dist}(v) + w(v, u) < \text{dist}(u): \quad \text{dist}(u) \leftarrow \text{dist}(v) + w(v, u)

This is called “relaxing” the edge $(v, u)$ . When no more relaxations are possible, all distances are optimal.

Greedy Strategy

Dijkstra's key insight: always process the unvisited vertex with the smallest tentative distance. This greedy choice is correct because edge weights are non-negative — no future path can improve the current minimum:

v^* = \arg\min_{v \notin S} \text{dist}(v)

A min-priority queue efficiently finds this minimum.

Complexity

With a binary min-heap priority queue:

T = O\bigl((|V| + |E|) \log |V|\bigr)

Each vertex is extracted once ( $O(|V| \log |V|)$ ) and each edge triggers at most one priority queue update ( $O(|E| \log |V|)$ ). With a Fibonacci heap this improves to $O(|V| \log |V| + |E|)$ .

Phase 2▶

See It Work

Dijkstra's algorithm from source A — greedy relaxation with a priority queue

Priority Queue (min-heap)

(0,A)

\text{dist}(s) = 0,\; \text{dist}(v) = \infty\; \forall v \neq s

Step 1 of 7

Initialize: set dist(A) = 0, all others = ∞. Push source A into the priority queue.

Phase 3</>

The Code

Mapping greedy relaxation to Python with heapq

Mathematical Formulation

\text{dist}(s) = 0,\; \text{dist}(v) = \infty

Initialize source distance to 0, all others to infinity

(d, v) = \text{extractMin}(PQ)

Greedily extract the vertex with smallest tentative distance

v \in S \Rightarrow \text{skip}

Skip already-finalized vertices (stale PQ entries)

\forall (v, u, w) \in E

Check all outgoing edges from the current vertex

\text{dist}(u) = \min(\text{dist}(u),\; \text{dist}(v) + w)

Relaxation: update distance if a shorter path is found

Python Implementation

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0                # Source distance
    pq = [(0, source)]              # Priority queue
    visited = set()

    while pq:
        d, v = heapq.heappop(pq)    # Extract min
        if v in visited: continue    # Skip stale
        visited.add(v)
        for u, w in graph[v]:        # Check neighbors
            if dist[v] + w < dist[u]:   # Relaxation
                dist[u] = dist[v] + w
                heapq.heappush(pq, (dist[u], u))
    return dist