Dijkstra's Algorithm

Dijkstra’s algorithm is a systematic way to find the cheapest route from one starting node to every other node in a network, when each connection has a nonnegative “cost” (distance, time, price, etc.). Imagine you’re standing at a starting intersection in a city and you want to know the shortest walking time to every other intersection. You begin by marking your starting point as distance 0. Then you repeatedly do a simple greedy ritual: (1) look among all intersections you can reach so far and pick the one with the smallest currently-known travel cost (the most promising frontier point), (2) “lock in” that cost as final because no later detour can beat it (this is only guaranteed when costs are nonnegative), and (3) try improving your best-known costs to its neighbors by checking whether going through this newly locked-in intersection yields a cheaper route (this check is often written conceptually as: newDistance = currentDistance + edgeWeight; if newDistance is smaller, replace the old estimate). By expanding outward from the start in order of increasing cost—like a ripple spreading through a pond—Dijkstra’s algorithm ensures that the first time you finalize a node, you have truly found the shortest path to it.

The algorithm was developed in the late 1950s, an era when computing was young and the practical need for efficient routing and planning was rapidly growing. Edsger W. Dijkstra reportedly conceived it in 1956 and published it in 1959. One of the often-told anecdotes is that he devised it while thinking about how to route in a network (including an example involving travel between Dutch cities). The core breakthrough is the elegant “greedy” insight: if all edge costs are nonnegative, then the next node with the smallest tentative distance can be safely finalized—an idea that turns a potentially explosive search into a disciplined, efficient procedure.

Pioneered by: Edsger W. Dijkstra (published 1959; conceived around 1956).

• GPS and mapping route planning (finding shortest driving time or distance, often as a subroutine within larger systems)
• Network routing and telecommunications (computing shortest paths in link-state routing-style models)
• Logistics and supply-chain optimization (least-cost paths through warehouses, hubs, and transportation lanes)
• Robotics and game AI pathfinding on weighted navigation graphs (movement costs across terrain)
• Dependency and workflow optimization (finding minimal-cost sequences in state graphs, scheduling-like problems)