How does your map app find the fastest route? Dijkstra’s algorithm, 1959. Grow a frontier outward from the start, always finalizing the CLOSEST unvisited node next, relaxing its neighbours’ distances. Because edge weights are non-negative, once a node is settled its distance can never improve — greedy, yet provably optimal. Slide the destination and read the shortest path.
Dijkstra’s algorithm finds shortest paths from a source in a graph with NON-NEGATIVE edge weights. It maintains tentative distances, repeatedly extracts the minimum-distance unsettled node, and RELAXES its edges (d[v] = min(d[v], d[u]+w)). Settling the closest node first is provably correct because no later, longer path can improve it. With a binary heap it runs in O((V+E)log V). It powers routing, maps, and network protocols. A fail-loud self-check throws unless it returns the known shortest distances on a test graph (0→3 = 4, 0→4 = 7). ◆ real graph algorithm, node-verified.
Requires non-negative weights (negative edges need Bellman–Ford); the greedy-yet-optimal property holds exactly under that condition. Shown on a fixed 5-node graph.