Dijkstra

Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative edge weights. O((V+E) log V) with a binary heap — the standard tool for routing, navigation, and network protocols (OSPF, IS-IS).

Complexity

How it works

Maintain dist[v] initialized to ∞ except dist[source] = 0, and a min-heap keyed by tentative distance. Repeatedly pop the closest unvisited node; relax each outgoing edge (v, w) — if dist[v] + weight < dist[w], update and push w. Once a node is popped, its distance is final (relies on edges being non-negative).

Python implementation

import heapq


def dijkstra(graph, source):
    """graph[u] = list of (v, weight). Returns dict of shortest distances."""
    dist = {n: float("inf") for n in graph}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                          # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist


graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("C", 2), ("D", 5)],
    "C": [("D", 1)],
    "D": [],
}
print(dijkstra(graph, "A"))   # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Trade-offs

• O((V+E) log V) with a binary heap; O(E + V log V) with a Fibonacci heap (rarely worth it).
• Requires non-negative edge weights — use Bellman-Ford if you have negatives.
• Doesn't handle changing weights; recompute from scratch on each query.
• For all-pairs shortest paths use Floyd-Warshall (O(V³)) or repeat Dijkstra V times.

← Back to Algorithms