How Dijkstra's Algorithm Works

Dijkstra needs a priority queue keyed by path cost, and Python's standard library ships one as heapq. That single import on line 34 is the only dependency the algorithm has; the heap is used as a min-priority queue with tuples that compare lexicographically (cost first, vertex second). The signature on line 37 takes three arguments: an adjacency-dict graph, a start vertex name, and an end vertex name. Notice that the function returns the shortest-path cost as a number rather than the path itself, which is enough for routing and queries but means a caller who needs the path must run a second pass with parent pointers. Three doctests pin the contract against expected costs of 6, 3, and 3, so a regression on the heap or visited logic fails CI before the PR can merge.

Three structures hold the entire state. Line 48 seeds the min-heap with a single tuple (0, start); the cost is zero because we have not yet moved. Line 49 is the visited set, empty at first. The outer loop on line 50 then repeatedly pops the cheapest unvisited vertex. The visited check on line 52 is what handles a wrinkle in this implementation: the same vertex may be pushed multiple times (once per incoming edge that improved the cost), so duplicates land in the heap and the visited set is what skips them on the second pop. Line 54 commits the current vertex as visited at its final cost, and line 55 returns immediately if that vertex is the destination. The algorithm exits the moment end is popped, which can be much sooner than visiting the entire graph.

Relaxation is the step that actually walks the graph. For every neighbor of the current vertex, the algorithm computes cost + c (the cost to reach the current vertex plus the edge weight to the neighbor) and pushes that tuple onto the heap. The visited check on line 58 skips neighbors that already have their final cost, which would otherwise cause useless pushes. There is no per-vertex distance-tracking dictionary in this implementation, no decrease-key operation; the cheapest path to any vertex is whichever copy of that vertex pops first. The trade-off is a heap that can hold up to E entries instead of V, but heappush and heappop both stay at O(log E) and the algorithm still runs in O((V + E) log V) overall. Line 62 returns -1 if the heap drains without reaching end, which is how unreachable destinations are signaled.

The graph format the algorithm consumes is the simplest one Python supports: a dict whose keys are vertex names and whose values are lists of [neighbor, edge_weight] pairs. Reading vertex E on line 70 shows it has two outgoing edges, one to B with weight 4 and one to F with weight 3. The doctest at the top of the file expects dijkstra(G, "E", "C") to return 6. Tracing by hand: from E the cheapest path is E to F (cost 3), then F to C (cost 3), totaling 6. The direct path E to B to A to C costs 4 + 2 + 5 = 11. Dijkstra finds the cheaper path because the heap pops F before B even though B is a direct neighbor, since 3 is less than 4.

The ASCII diagram on lines 75 through 81 is what makes this file read like a textbook chapter rather than a code listing. It draws G2 as a line of five vertices with weight-1 edges, plus a single weight-3 shortcut edge from E to F. Below the diagram, the dict on lines 82 through 88 encodes the same graph in the format the algorithm reads. A doctest then expects dijkstra(G2, "E", "F") to return 3 because the shortcut and the long path through B, C, D both have total cost 3, and Dijkstra correctly returns 3 either way. Together, the diagram and the dict make the test self-explanatory; a contributor who edits the algorithm and breaks the tie-break logic immediately sees which graph caught the regression by reading the picture above the failing test.

Like merge_sort.py and unlike quick_sort.py, this file runs doctest.testmod() the moment it is invoked directly. That means a contributor running python3 graphs/dijkstra.py sees every doctest in the function docstring execute against the in-file graphs G, G2, and G3, with any mismatch raising a clear failure message. The file already calls dijkstra three times on lines 107, 110, and 113 with print statements, so execution prints 6, 3, and 3 above the doctest summary line. This is the canonical shape for a graph-algorithm file in this repository: import, function, in-file example graphs, calls that print expected output, and a doctest runner under __main__. The Bellman-Ford file at graphs/bellman_ford.py follows the same five-section pattern.