Dijkstra's Algorithm

Every time you ask a map app for the fastest route, something underneath is solving the shortest-path problem: given a network of places and roads with travel costs, find the cheapest way from your starting point to everywhere else.

Edsger W. Dijkstra solved it elegantly in 1959, during a coffee break in Amsterdam — by hand, with no computer, in twenty minutes. His insight: always extend the shortest known path first. Commit to one node at a time, in order of increasing distance, and you will never have to revise a decision.

The result is a provably correct, polynomial-time algorithm. Unlike P vs NP questions or NP-hard scheduling problems, finding the shortest path is genuinely easy — not just fast in practice, but fast in theory, with a mathematical proof of optimality attached.

Below is a small weighted graph with eight nodes. Node A is the source. Click Step to advance Dijkstra's algorithm one edge relaxation at a time, or Run to watch it finish automatically.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="info">
  <div id="queue-box" class="queue-box"><span class="label">{{queue_label}}</span> <span id="queue-txt">—</span></div>
  <div id="msg" class="msg">{{initial_msg}}</div>
</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; background: #f5f7fa; border: 1px solid #d0d7de; border-radius: 10px; max-width: 100%; }
.info { margin: .5rem 0; }
.queue-box { font-size: .85rem; color: #333; margin-bottom: .25rem; }
.label { font-weight: 600; }
.msg { font-size: .95rem; font-weight: 600; min-height: 1.4em; }
.msg.ok { color: #0a7d33; }
.msg.relax { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the priority queue: the algorithm always picks the unvisited node with the smallest tentative distance. Once a node turns green it is settled — its distance is final and will never improve. That greedy guarantee is the heart of Dijkstra's proof of correctness.

Dijkstra's algorithm is a solved problem — provably optimal for graphs with non-negative weights, published by Edsger W. Dijkstra in 1959.

• How it works: maintain a priority queue of (distance, node) pairs. Repeatedly extract the minimum-distance unvisited node, then relax each outgoing edge: if the new path through this node is shorter than the known distance to the neighbor, update it.
• Correctness: because all edge weights are non-negative, once a node is extracted from the queue its distance cannot decrease further. The greedy choice is always safe.
• Time complexity: with a binary heap, O((V + E) log V). With a Fibonacci heap, the asymptotically optimal $O(E + V \log V)$. For dense graphs (E ≈ $V^{2}$), even a simple array gives $O(V^{2})$ which is competitive.
• The negative-weight catch: if any edge weight is negative, the greedy assumption breaks. Bellman–Ford ($O(VE)$) handles negative weights; detecting negative cycles requires an extra pass.
• It is in P: shortest paths with non-negative weights are not hard — they sit firmly in polynomial time, with no open questions about their complexity. This puts them in a different universe from NP-complete problems.

The algorithm's elegance is that the priority queue does all the work: it automatically selects the next-closest unfinished node, and the relaxation step propagates information in the only direction that matters.

Shortest-path problems appear whenever resources flow through a network, and Dijkstra's algorithm is the standard answer:

• GPS and navigation: every map app uses a variant of Dijkstra (often accelerated by A* heuristics) to find the fastest route from A to B.
• Internet routing (OSPF, IS-IS): backbone routers run link-state protocols that build a shortest-path tree over the entire network topology every time a link changes.
• Game AI: characters in video games find their way around obstacles using Dijkstra or A* on a grid or navigation mesh.
• Network analysis: finding the most reliable or lowest-latency path in a telecommunications network is a shortest-path problem with costs defined by latency or failure probability.
• Robotics and planning: motion planners represent configuration space as a graph and use Dijkstra to find collision-free paths.

The reason Dijkstra appears in so many places is that "minimize cumulative cost along a path" is an abstraction that covers an enormous range of real decisions. Unlike NP-hard problems, you do not have to settle for approximations — you get the exact optimum, every time, fast.

Dijkstra's algorithm is one of the rare places in computer science where every question has a clean answer. The problem is well-defined, the algorithm is correct, the complexity is settled, and the optimality is proven — all in a result that fits on a single page of a 1959 paper.

It also teaches a broader lesson: not every optimization problem is hard. The difficulty you meet in NP-complete problems is real, but it is not universal. Some problems — including the one your phone solves every time you ask for directions — sit firmly in polynomial time, accessible to exact algorithms that never need to guess.

The next time your map app finds a route in milliseconds across a graph of millions of roads, you are seeing Dijkstra's twenty-minute coffee-break insight at work, scaled up by decades of engineering but still recognizably the same greedy idea: always extend the shortest known path first.