Visualizer CodeViz · Algorithms, visualized

Part II · Shortest paths · week 4

Dijkstra's algorithm

Repeatedly settle the unsettled vertex closest to the source and relax its edges. Non-negative weights are what make a settled distance final.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(E log V)
requiresno negative weights
each edgerelaxed exactly once
structuremin priority queue

Reference: Sedgewick & Wayne, §4.4; Dijkstra 1956.

Dijkstra's algorithm in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

import heapq

class DijkstraSP:
    # Grow a shortest-paths tree from s. Always settle the unsettled vertex
    # with the smallest dist_to: because no weight is negative, no path
    # discovered later can be shorter, so that value is FINAL.

    def __init__(self, digraph, s):
        self.dist_to = [float('inf')] * digraph.V
        self.edge_to = [None] * digraph.V
        self.dist_to[s] = 0.0
        done = [False] * digraph.V
        pq = [(0.0, s)]
        while pq:
            d, v = heapq.heappop(pq)      # nearest unsettled vertex
            if done[v]:
                continue                  # a stale entry -- ignore it
            done[v] = True                # dist_to[v] is now final
            for w, weight in digraph.adj(v):
                if self.dist_to[w] > self.dist_to[v] + weight:
                    self.dist_to[w] = self.dist_to[v] + weight   # RELAX
                    self.edge_to[w] = v
                    heapq.heappush(pq, (self.dist_to[w], w))

Why it works

Relaxation is the only operation

Relaxing edge v→w means: if going to w via v is shorter than the best known route to w, record the improvement. Every shortest-path algorithm in the course is a different order of relaxations — Dijkstra by nearest-first, acyclic SP by topological order, Bellman–Ford by brute-force passes. The optimality conditions are the same for all of them: no edge can be relaxed any further.

Why non-negative weights matter

When v is settled, every unsettled vertex is at least as far away, and any route through them adds only non-negative weight — so dist_to[v] can never improve again. Introduce one negative edge and that argument collapses: a longer-looking detour can turn out cheaper, and Dijkstra will already have committed. Negative weights need Bellman–Ford, not a tweak to this code.

The stale-entry trick

A textbook Dijkstra uses an indexed priority queue and decrease_key. Python's heapq has no such operation, so the idiom is to push a new entry on every improvement and skip entries for vertices already settled. Slightly more memory, same asymptotic cost, far less code — and it is what most production Python does.

Where you meet it

Routing (network and road), where a good implementation on a continental road network answers queries in milliseconds after preprocessing; also arbitrage detection, seam carving, scheduling and any “cheapest way to get from A to B” problem where costs cannot be negative. Note it computes shortest paths to every vertex, not just one — stop early at your target if that is all you need.

What to try in the animation

v-w:weight means v → w. The default is tinyEWD.txt from the course.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Dijkstra's algorithm in the player →

The rest of Shortest paths