Graph Algorithms9 min read

Dijkstra's Algorithm

Always extend the cheapest road first — GPS navigation for graphs
binary heap:\(O((V+E)\) log V)Fibonacci heap:\(O(E + V \log V)\)requirement:No negative edge weights

Imagine planning a road trip. You want the cheapest route from your city to every other city. Your GPS strategy: always extend the cheapest reachable road next.

Start at home (cost 0). Look at all roads leaving home, note their costs. The cheapest one? Lock it in — that destination's shortest path is confirmed. From there, look at all roads leaving that city, update any costs if you found a cheaper route. Always pick the next cheapest unvisited destination. Repeat until you've reached everywhere.

That's Dijkstra's algorithm — a greedy strategy that works because non-negative road costs mean you can never make a route cheaper by going farther first.

The Relaxation Step

Every vertex v has a tentative distance dist[v], initially infinity (unreachable) except for the source (dist[s] = 0).

Relaxation: when processing vertex u, for each neighbor v, check: "Is going through u to v cheaper than what we've found so far?" If dist[u] + weight(u,v) < dist[v], update dist[v]. That's it. The whole algorithm is just choosing which vertex to relax next (always the one with the smallest current dist) and doing this until all vertices are settled.

Why a Priority Queue?

The key operation is: "which unvisited vertex has the smallest current distance?" A binary min-heap answers this in \(O(\log V)\) per extraction. Total cost: \(O((V+E)\) log V) — near-linear for sparse graphs.

In practice, most implementations use a lazy deletion approach: when you find a shorter path to v, just push a new entry (dist, v) into the heap. When you extract a vertex and its stored distance is larger than the current dist[v], it's stale — skip it. This avoids needing a decrease-key operation while achieving the same asymptotic complexity.

Why Negative Weights Break It

Dijkstra's correctness rests on one guarantee: once a vertex is finalized, no shorter path to it will ever be found. With non-negative weights, adding more edges can only increase or maintain path length — so the minimum unvisited vertex is always safe to finalize.

A single negative edge can shatter this. Say vertex v is finalized at distance 5. Later you discover edge u → v with weight −3, giving a total of 4. Dijkstra missed it. For graphs with negative weights, use Bellman-Ford instead.

Dense vs. Sparse Graphs

For sparse graphs (E ≈ V), the heap-based \(O((V+E)\) log V) ≈ \(O(V \log V)\) is excellent. For dense graphs (E ≈ \(V^2\)), a simple \(O(V^2)\) array scan (linear search for the minimum) can actually beat the heap-based version, since \(O(V^2 \log V)\) > \(O(V^2)\).

Note: Dijkstra is greedy: it bets that the cheapest reachable vertex so far is definitely reached optimally. With non-negative weights, this bet is always correct — no future path can sneak in and be cheaper. Negative weights break the bet.

Dijkstra's Algorithm with a Priority Queue

import heapq


def dijkstra(graph, src):
    """
    graph: dict of {u: [(v, weight), ...]}
    Returns dist[] — shortest distance from src to all nodes.
    """
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]  # (cost, node)


    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:   # stale entry — skip
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))


    return dist


graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8)],
    'D': []
}
dist = dijkstra(graph, 'A')
for node, d in sorted(dist.items()):
    print(f"A -> {node}: {d}")
Output
A -> A: 0
A -> B: 3
A -> C: 2
A -> D: 8

Complexity

⚡ Binary min-heap
Standard implementation; each edge triggers at most one heap push
Near-linear for sparse graphs \(O((V+E)\) log V)
🚀 Fibonacci heap
Amortized \(O(1)\) decrease-key; complex to implement, rarely seen in practice
Optimal for dense graphs \(O(E + V \log V)\)
📋 Unsorted array scan
Simple linear scan for minimum; beats the heap when E ≈ \(V^2\)
Quadratic — best for dense graphs \(O(V^2)\)
🚫 Negative weights
Greedy invariant breaks — use Bellman-Ford or SPFA instead
Not supported Undefined

Quick check

Dijkstra processes vertex v and finalizes its distance at 7. Can a shorter path to v be found later?

Continue reading