Dijkstra's Algorithm

How it works, step by step

1. 1

   Give every node a tentative distance: 0 for the start, ∞ for everyone else.

2. 2

   Pick the unsettled node with the smallest tentative distance and settle it. Its distance is now final.

3. 3

   Why is that safe? Any other route into it must leave the settled region through a node that is already at least as far away - and with no negative weights, the route cannot get cheaper from there.

4. 4

   Relax each edge leaving the settled node: if `dist[u] + weight < dist[v]`, you found a cheaper way to v - update its distance and remember the edge you came through.

5. 5

   Repeat until every node is settled. The remembered edges form a shortest-path tree: one best route from the start to every node.

6. 6

   With a priority queue doing the "pick the smallest" step, the total work is O(E log V).

The code, in JavaScript

function dijkstra(graph, start) {
  const dist = {};
  const settled = new Set();
  for (const node in graph) dist[node] = Infinity;
  dist[start] = 0;

  for (let i = 0; i < Object.keys(graph).length; i++) {
    // Linear scan: the unsettled node with the smallest tentative distance.
    let u = null;
    for (const node in graph) {
      if (!settled.has(node) && (u === null || dist[node] < dist[u])) u = node;
    }
    if (dist[u] === Infinity) break;   // everything left is unreachable
    settled.add(u);                    // dist[u] is final from here on

    for (const [v, w] of graph[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;         // relax: found a cheaper way to v
      }
    }
  }
  return dist;
}

const graph = {
  A: [["B", 10], ["C", 2]],
  B: [["A", 10], ["C", 3], ["D", 4]],
  C: [["A", 2], ["B", 3], ["D", 4], ["E", 7]],
  D: [["B", 4], ["C", 4], ["E", 1], ["F", 6]],
  E: [["C", 7], ["D", 1], ["F", 2], ["G", 6]],
  F: [["D", 6], ["E", 2], ["G", 2]],
  G: [["E", 6], ["F", 2]],
};

dijkstra(graph, "A");
// → { A: 0, B: 5, C: 2, D: 6, E: 7, F: 9, G: 11 }
// Note B: the 2-hop route A→C→B (2+3=5) beats the direct A→B road (10).

Dry run: Dijkstra from node A

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• One negative edge quietly breaks the settled-is-final promise. Take directed edges A→B=2, B→D=2, A→C=5, C→B=-4. Dijkstra settles B at 2 and computes D=4. The cheaper way to B (via C, cost 1) is found too late: B is already settled, so D is never re-checked. The true cost of D is 1+2=3. Negative weights are Bellman-Ford's job.
• JavaScript has no built-in priority queue, so people improvise: `queue.sort()` every iteration, or a minimum-scan of an array inside the main loop. It returns correct answers - and quietly ships the O(V²) version. Fine at 1,000 nodes, painful at 1,000,000.
• You do not need decrease-key. Textbook heaps update a node's priority in place, which is fiddly to code. The practical trick is lazy deletion: on improvement just push a new [dist, node] pair and skip stale pairs on pop. The heap grows to O(E) entries, but O(E log E) is still O(E log V).
• With lazy deletion, forgetting `if (d > dist[u]) continue` still returns correct distances - which is why nobody notices. But every stale pop re-relaxes all of u's edges and pushes even more duplicates. The complexity quietly inflates, and on dense graphs it shows up as mystery slowness.

Dijkstra's Algorithm vs. its closest relatives