Introduction

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.

Try It

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">Node <b>A</b> is the source. Each edge shows its weight. Click <b>Step</b> to relax one edge at a time โ€” the algorithm always picks the unvisited node with the smallest tentative distance. Green nodes are <b>settled</b> (distance final).</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="info">
  <div id="queue-box" class="queue-box"><span class="label">Priority queue:</span> <span id="queue-txt">โ€”</span></div>
  <div id="msg" class="msg">Press Step or Run to start Dijkstra from A.</div>
</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dijkstra's algorithm โ€” step-by-step visualization on a small weighted graph.
// Nodes: A-H placed on a canvas. Edges have non-negative integer weights.
// The algorithm uses a min-heap (simulated with a sorted array for clarity).
// Once a node is "settled" (extracted from the queue) its distance is final โ€”
// that is the core invariant that makes Dijkstra correct for non-negative weights.

const NODES = {
  A: { x: 60,  y: 150, label: 'A' },
  B: { x: 160, y: 60,  label: 'B' },
  C: { x: 160, y: 240, label: 'C' },
  D: { x: 260, y: 150, label: 'D' },
  E: { x: 260, y: 50,  label: 'E' },
  F: { x: 260, y: 250, label: 'F' },
  G: { x: 380, y: 100, label: 'G' },
  H: { x: 380, y: 220, label: 'H' }
};
const EDGES = [
  ['A','B',4], ['A','C',2],
  ['B','D',5], ['B','E',1],
  ['C','D',8], ['C','F',10],
  ['D','G',2], ['D','H',6],
  ['E','G',3],
  ['F','H',4],
  ['G','H',1]
];

// Build adjacency list
const adj = {};
Object.keys(NODES).forEach(n => adj[n] = []);
EDGES.forEach(([u, v, w]) => { adj[u].push([v, w]); adj[v].push([u, w]); });

const INF = Infinity;
let dist, prev, settled, queue, relaxLog, stepIdx, done;

function initAlgo() {
  dist = {}; prev = {}; settled = new Set(); queue = []; relaxLog = []; stepIdx = 0; done = false;
  Object.keys(NODES).forEach(n => { dist[n] = INF; prev[n] = null; });
  dist['A'] = 0;
  queue.push([0, 'A']);
}

// Pre-compute all steps so we can replay them
function precompute() {
  // work on clones
  const d = {...dist}; const s = new Set(); const q = [[0,'A']];
  const log = [];
  while (q.length) {
    q.sort((a,b) => a[0]-b[0]);
    const [du, u] = q.shift();
    if (s.has(u)) continue;
    s.add(u);
    log.push({ type: 'settle', node: u, dist: du, queue: q.map(x=>x[1]+':'+x[0]).join(', ') });
    for (const [v, w] of adj[u]) {
      if (s.has(v)) continue;
      const nd = du + w;
      if (nd < d[v]) {
        d[v] = nd;
        prev[v] = u;
        q.push([nd, v]);
        log.push({ type: 'relax', from: u, to: v, newDist: nd, queue: q.map(x=>x[1]+':'+x[0]).join(', ') });
      }
    }
  }
  return { log, finalDist: d, finalPrev: prev };
}

let allSteps, finalDist, finalPrev;

function reset() {
  initAlgo();
  const r = precompute();
  allSteps = r.log; finalDist = r.finalDist; finalPrev = r.finalPrev;
  stepIdx = 0; done = false;
  // reset visual state
  dist = {}; prev = {}; settled = new Set();
  Object.keys(NODES).forEach(n => { dist[n] = INF; prev[n] = null; });
  dist['A'] = 0;
  draw();
  document.getElementById('msg').textContent = 'Press Step or Run to start Dijkstra from A.';
  document.getElementById('msg').className = 'msg';
  document.getElementById('queue-txt').textContent = 'A:0';
}

function applyStep() {
  if (done || stepIdx >= allSteps.length) { done = true; return; }
  const s = allSteps[stepIdx++];
  if (s.type === 'settle') {
    settled.add(s.node);
    dist[s.node] = s.dist;
    document.getElementById('queue-txt').textContent = s.queue || 'โ€”';
    document.getElementById('msg').textContent = fmt('Settled %node% with distance %dist%.', { node: s.node, dist: s.dist });
    document.getElementById('msg').className = 'msg ok';
  } else {
    dist[s.to] = s.newDist;
    prev[s.to] = s.from;
    document.getElementById('queue-txt').textContent = s.queue || 'โ€”';
    document.getElementById('msg').textContent = fmt('Relaxed %from%โ†’%to% โ†’ new dist %newDist%.', { from: s.from, to: s.to, newDist: s.newDist });
    document.getElementById('msg').className = 'msg relax';
  }
  if (stepIdx >= allSteps.length) {
    done = true;
    document.getElementById('queue-txt').textContent = 'โ€”';
    document.getElementById('msg').textContent = 'โœ“ Done! Shortest-path tree from A complete.';
    document.getElementById('msg').className = 'msg ok';
  }
  draw();
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

function nodeColor(n) {
  if (settled.has(n)) return '#2ecc71';   // settled = green
  if (dist[n] < INF)  return '#f9c74f';   // reached = yellow
  return '#c9ccd1';                         // unreached = grey
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw settled-path tree edges in green
  const treeEdges = new Set();
  Object.keys(NODES).forEach(n => { if (prev[n]) treeEdges.add(prev[n]+'-'+n); });

  // Edges
  EDGES.forEach(([u, v, w]) => {
    const a = NODES[u], b = NODES[v];
    const inTree = treeEdges.has(u+'-'+v) || treeEdges.has(v+'-'+u);
    ctx.beginPath();
    ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y);
    ctx.strokeStyle = inTree ? '#0a7d33' : '#adb5bd';
    ctx.lineWidth = inTree ? 2.5 : 1.5;
    ctx.stroke();
    // Weight label
    const mx = (a.x+b.x)/2, my = (a.y+b.y)/2;
    ctx.fillStyle = '#555';
    ctx.font = '12px system-ui, sans-serif';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(w, mx, my - 7);
  });

  // Nodes
  Object.entries(NODES).forEach(([id, n]) => {
    ctx.beginPath();
    ctx.arc(n.x, n.y, 20, 0, Math.PI*2);
    ctx.fillStyle = nodeColor(id);
    ctx.fill();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 1.8;
    ctx.stroke();

    ctx.fillStyle = '#1d3557';
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(id, n.x, n.y);

    // Distance label above node
    const d = dist[id];
    const lbl = (d === INF) ? 'โˆž' : String(d);
    ctx.fillStyle = '#444';
    ctx.font = '11px system-ui, sans-serif';
    ctx.fillText(lbl, n.x, n.y - 28);
  });
}

let running = false;
function runAll() {
  if (done) return;
  running = true;
  function tick() {
    if (done || !running) { running = false; return; }
    applyStep();
    setTimeout(tick, 300);
  }
  tick();
}

document.getElementById('step').addEventListener('click', () => { running = false; applyStep(); });
document.getElementById('run').addEventListener('click', runAll);
document.getElementById('reset').addEventListener('click', () => { running = false; reset(); });

reset();
Result
Console

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.

The Real Complexity

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+VlogโกV)O(E + V \log V). For dense graphs (E โ‰ˆ V2V^{2}), even a simple array gives O(V2)O(V^{2}) which is competitive.
  • The negative-weight catch: if any edge weight is negative, the greedy assumption breaks. Bellmanโ€“Ford (O(VE)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.

Where It 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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dijkstra/Content licensed under CC BY-NC 4.0.