Find the cheapest route through a weighted map by always settling the nearest unfinished place, then relaxing its neighbours. It is greedy and it is exact — for non-negative weights, the first time a place is settled its distance is final. The one part that wants speed is pulling the nearest place each step: a priority queue — the heap the suggestion box lists.
THE TECHNIQUE settle the nearest, relax its edges
Keep a tentative distance to every cell (0 at the start, ∞ elsewhere). Repeatedly take the unsettled cell of smallest distance, mark it final, and relax each neighbour: if going through here is cheaper, lower it. Each cell here carries a step-cost 1–9; the search settles cells in rings of increasing cost (no hunch, unlike A*’s beeline) and finds the cheapest corner-to-corner path. live demo
HISTORY & CREDIT designed in his head, over coffee
A cornerstone of his fame — and he thought it a throwaway twenty-minute demo, invented with no pencil and paper. cited
1956 · shopping in Amsterdam with his fiancee Ria, Dijkstra sits down for coffee and, in about twenty minutes and without pencil or paper, designs the shortest-path algorithm — a demo for the ARMAC computer (Rotterdam→Groningen, the Dutch map reduced to 64 cities so a city number fit in 6 bits). his words · “Eventually, that algorithm became, to my great amazement, one of the cornerstones of my fame.” He rated his programming-methodology work higher. 1957 · Leyzorek, Gray, Johnson et al. describe the same method independently — the name stuck to Dijkstra partly because no one wants to cite a seven-author algorithm. the heap myth · the fast O(E log V) “Dijkstra” relies on a binary heap (Williams, 1964) or Fibonacci heap (Fredman-Tarjan, 1984) — structures Dijkstra never used. His own 1959 version is the O(V²) linear scan.
The paper solves two problems; its first (a spanning tree) rediscovered Jarnik’s 1930 method — the one usually miscalled “Prim’s.” tangled priority
RECOMMEND FOR I-13 the queue the box lists — and the authentic form runs
Two array primitives make Dijkstra. Relaxing dist[] is the same array-relax dart 046 (Bellman-Ford) already runs. The other is extract-min — a linear scan over dist[] for the nearest unsettled node — which runs on the real compiler:
$ i13 run amin.i13 # extract-min: linear scan over the dist[] array
m = 2 # the nearest unsettled node (dist [7,3,9,2,8,5])
Recommend: presses PS-005 (a binary heap / priority queue) — the extract-min above is O(n) by linear scan, which a heap makes O(log n). But the honest twist: I-13 today runs the AUTHENTIC Dijkstra — his own 1959 algorithm was the O(V²) linear scan; the binary heap is Williams (1964), a later graft. So the array runs the real thing; the heap is the optimization the box lists. Also: the natural return is (distance map, predecessor tree) — two arrays at once — a fourth nudge toward the multiple-return frontier (with quicksort-045, union-find-048, A*-052).