Dijkstra's Algorithm

Single-source shortest paths with non-negative weights. Greedily settles the closest unsettled node — once settled, a node's distance is provably final. GPS routing at its core.

Category: Graphs
Time complexity: O(E log V)
Space complexity: O(V)

Pseudocode

dist[start] ← 0
settle closest unsettled node
relax its outgoing edges
repeat until all settled

Reference implementation

dist = {start: 0}
pq = [(0, start)]
while pq:
    d, n = heappop(pq)
    for m, w in adj[n]:
        if d + w &lt; dist.get(m, ∞):
            dist[m] = d + w

Open the interactive Dijkstra's Algorithm visualisation →