Dijkstra's Algorithm Visualization — Step by Step

The distance table

Dijkstra's algorithm maintains one central piece of state: a table of the best known distance from the start to every node, alongside a *previous node* pointer for path reconstruction. Take a five-node graph with weighted edges 0–1 (4), 0–2 (1), 1–2 (2), 1–3 (1), 2–3 (5), and 3–4 (3). Initially only the start is reachable for free: dist = [0, ∞, ∞, ∞, ∞]. The ∞ entries mean "no path found yet". The algorithm's whole job is to tighten this table until every entry is provably the true shortest distance.

Greedy selection: finalize the closest node

Each round picks the unfinalized node with the smallest known distance and locks it in. First round: node 0 wins with distance 0. Why is locking safe? Because every edge weight is non-negative, any other route to that node would have to travel through a node that is already *farther away* — it could never come back cheaper. This is the greedy insight the whole algorithm rests on, and precisely the step that breaks if negative edges exist. In the visualizer, selection and finalization appear as distinct steps, and finalized nodes never change again.

Relaxation: offering shorter routes

After finalizing a node, examine each edge leaving it and ask: does going *through this node* beat the neighbour's current best? Finalizing node 0 relaxes its edges: node 1 improves from ∞ to 0 + 4 = 4, node 2 from ∞ to 0 + 1 = 1. Table: [0, 4, 1, ∞, ∞]. Next round finalizes node 2 (distance 1, the smallest) and relaxes its edges: node 1 improves from 4 to 1 + 2 = 3 — the detour through 2 beats the direct edge — and node 3 gets 1 + 5 = 6. Table: [0, 3, 1, 6, ∞].

Finishing the trace

Round three finalizes node 1 (distance 3). Relaxing its edge to node 3 offers 3 + 1 = 4, beating 6 — node 3 improves again and its previous-pointer switches to node 1. Table: [0, 3, 1, 4, ∞]. Round four finalizes node 3 (distance 4) and relaxes 3–4: node 4 gets 4 + 3 = 7. Round five finalizes node 4; nothing is left. Final distances: [0, 3, 1, 4, 7]. Notice how node 3 was improved twice — early estimates are provisional, and only finalization makes a distance permanent.

Reconstructing the path

The distance table says node 4 costs 7, and the previous-pointers say how: 4 ← 3 ← 1 ← 2 ← 0. Reversed, the shortest path is 0 → 2 → 1 → 3 → 4 with weights 1 + 2 + 1 + 3 = 7. Compare the tempting direct-looking route 0 → 1 → 3 → 4: it costs 4 + 1 + 3 = 8. This is why BFS fails on weighted graphs — it would happily take the fewer-hop route and be wrong. Dijkstra counts *weight*, not hops, and provably minimizes it.

Complexity and the priority queue

The version visualized here scans the whole table for the minimum each round — O(V) per selection, O(V²) total, which is simple and perfectly fine for dense or small graphs. Production implementations store the frontier in a min-heap (priority queue), making each selection O(log V) and each relaxation O(log V), for O((V + E) log V) overall — a huge win on sparse graphs like road networks. Either way the answers are identical; only the cost of repeatedly asking "which node is closest?" changes.

JavaScript

// Uses an O(V) array scan for the minimum instead of a heap, for clarity.
function dijkstra(graph, start) {
  // graph: { node: [{ node, weight }, ...] }
  const nodes = Object.keys(graph);
  const dist = {};
  const prev = {};
  const finalized = new Set();

  for (const node of nodes) dist[node] = Infinity;
  dist[start] = 0;

  while (finalized.size < nodes.length) {
    let u = null; // closest unfinalized node
    for (const node of nodes) {
      if (!finalized.has(node) && (u === null || dist[node] < dist[u])) {
        u = node;
      }
    }
    if (u === null || dist[u] === Infinity) break; // rest unreachable
    finalized.add(u);

    for (const { node: v, weight } of graph[u]) {
      if (dist[u] + weight < dist[v]) { // relax
        dist[v] = dist[u] + weight;
        prev[v] = u;
      }
    }
  }
  return { dist, prev };
}

Python

def dijkstra(graph, start):
    """graph: dict mapping node -> list of (neighbor, weight) pairs.

    Uses an O(V) scan for the minimum instead of a heap, for clarity.
    """
    dist = {node: float('inf') for node in graph}
    prev = {}
    dist[start] = 0
    finalized = set()

    while len(finalized) < len(graph):
        u = min(
            (n for n in graph if n not in finalized),
            key=lambda n: dist[n],
            default=None,
        )
        if u is None or dist[u] == float('inf'):
            break  # remaining nodes are unreachable
        finalized.add(u)

        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:  # relax
                dist[v] = dist[u] + weight
                prev[v] = u

    return dist, prev

Java

import java.util.*;

public class Dijkstra {
    // Uses an O(V) scan for the minimum instead of a heap, for clarity.
    // graph[u] = list of {neighbor, weight} pairs.
    public static int[] dijkstra(int[][][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] finalized = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int round = 0; round < n; round++) {
            int u = -1; // closest unfinalized node
            for (int v = 0; v < n; v++) {
                if (!finalized[v] && (u == -1 || dist[v] < dist[u])) u = v;
            }
            if (u == -1 || dist[u] == Integer.MAX_VALUE) break;
            finalized[u] = true;

            for (int[] edge : graph[u]) {
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) { // relax
                    dist[v] = dist[u] + w;
                }
            }
        }
        return dist;
    }
}