ZERO / HERO
Always explore the nearest unvisited town

Dijkstra's Algorithm

The analogy

You are mapping travel times from home. You keep a best-known time to every town, all starting at infinity. Then you repeatedly walk to the nearest town you have not settled yet, and from there check whether going through it gives a faster route to its neighbours. Because you always settle the closest one first, once a town is settled you can never find a shorter way to it.

Visualizer

Dijkstra's frontier

step 1 / 12
A 0B ∞C ∞D ∞E ∞F ∞

Every distance starts at infinity except the source A, which is 0. The heap holds candidates ordered by tentative distance.heap: [(0, A)]

import heapq

def dijkstra(g, src):
    dist = {src: 0}
    parent = {}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue                     # stale entry
        for v, w in g[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u            # for path recovery
                heapq.heappush(pq, (nd, v))
    return dist, parent

# O((V + E) log V). NON-NEGATIVE weights only.
Check yourself

Your graph has one edge of weight −3. What does Dijkstra do?