Dijkstra's Algorithm Visualizer

Edsger Dijkstra designed this algorithm in 1956, in about twenty minutes, in a café in Amsterdam, while his fiancée was shopping. He was trying to demonstrate the capabilities of a new computer to a non-technical audience, and he needed a problem everyone could understand: the shortest route between two cities. He did not write it down for another three years.

It is now the algorithm behind essentially every route you have ever been given by a navigation system, every packet routed across the internet by OSPF, and every pathfinding system in games that cares about terrain cost. The idea is a single greedy insight: the nearest unvisited node's distance is already final, because any other route to it would have to pass through something even further away.

What is Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path from one source node to every other node in a graph with non-negative edge weights. It maintains a tentative distance for each node — the best route found so far — starting at zero for the source and infinity for everything else.

Repeatedly, it selects the unvisited node with the smallest tentative distance, declares that distance final, and relaxes each of its outgoing edges: if reaching a neighbour through this node is cheaper than the neighbour's current best, the neighbour's distance is lowered.

Structurally it is breadth-first search with the queue replaced by a priority queue. BFS takes the node that has been waiting longest; Dijkstra takes the node that is cheapest to reach. On a graph where every edge costs 1, the two make identical choices — Dijkstra is the generalisation of BFS to weighted graphs.

Why the greedy choice is safe

The claim is: when a node is selected as the closest unvisited one, its tentative distance is already the true shortest distance. This is not obvious, and the argument for it is the heart of the algorithm.

Suppose node u is selected with tentative distance d, but a genuinely shorter path P to u exists. P starts at the source, which is visited, and ends at u, which is not — so somewhere along it there is a first unvisited node, call it x, reached only through visited nodes. Because x is reached entirely through settled nodes, its tentative distance already equals the length of P up to x. Since the remaining portion of P from x to u has non-negative length, the distance to x is at most the length of P, which we assumed is less than d. But then x, not u, would have been the smallest unvisited node. Contradiction.

Notice exactly where non-negativity enters: the step that says the remainder of the path cannot reduce the total. With a negative edge, a longer-looking prefix could still lead to a cheaper total, and the whole argument collapses.

Step-by-step walkthrough

A graph with A–B cost 4, A–C cost 2, C–B cost 1, B–D cost 5, C–D cost 8. Start at A.

1. Distances: A=0, everything else infinity. Settle A (distance 0). Relax A→B to 4 and A→C to 2.
2. Smallest unvisited is C at 2. Settle it. Relax C→B: 2 + 1 = 3, which beats B's current 4, so lower B to 3. Relax C→D: 2 + 8 = 10, so D becomes 10.
3. Smallest unvisited is now B at 3. Settle it. Relax B→D: 3 + 5 = 8, which beats 10, so D drops to 8.
4. Settle D at 8. Every node is settled. Final distances: A=0, C=2, B=3, D=8.
5. The shortest route to D is A→C→B→D, three edges costing 8 — while the direct-looking A→C→D uses fewer edges and costs 10. This is precisely why BFS gives the wrong answer on weighted graphs.

The priority queue is the whole cost

Finding the smallest unvisited distance is the operation that dominates the running time, and how you implement it determines the complexity.

Linear scan over all nodes each iteration gives O(V²). This sounds bad and is actually the right choice for dense graphs, where E approaches V² — you cannot beat it, and it avoids all heap overhead.

Binary heap gives O((V + E) log V), which is the standard implementation and the right default for sparse graphs. Each edge relaxation may push an updated distance, and each node extraction costs log V.

Fibonacci heap gives the theoretical optimum of O(E + V log V), because decrease-key becomes O(1) amortised. In practice its constant factors are large enough that it rarely wins on real graph sizes — it is an important theoretical result and a poor engineering default.

One practical detail matters more than the heap choice: most standard-library priority queues have no decrease-key operation. The usual workaround is lazy deletion — push a new entry with the improved distance and leave the stale one in the heap, skipping any entry whose distance no longer matches when it is popped. The heap can hold up to E entries instead of V, which is a memory cost, but the code is far simpler and the asymptotics are unchanged.

How the animation above works

The distance table is the thing to watch, not the graph. Values start at ∞ and drop as edges are relaxed — sometimes several times for the same node, each drop representing a better route found. When a node is settled it turns mint and its number stops changing forever.

The revealing moment is a rejected relaxation: the visualiser explicitly shows edges where the candidate distance was no better than the known one. Those are the comparisons that would be missing from a BFS, and they are where the algorithm earns its correctness.

Set a destination node and Dijkstra stops the moment that node is settled, then draws the path in coral. Try it with a destination whose cheapest route uses more edges than the obvious one — the path highlighted will not be the one that looks shortest on screen.

Time and space complexity

O((V + E) log V) with a binary heap — the standard implementation. Each vertex is extracted once at O(log V), and each edge can trigger a heap insertion at O(log V).

O(V²) with a simple array, which is better for dense graphs where E ≈ V², since (V + V²)·log V exceeds V². The right choice genuinely depends on graph density, and this is one of the few places where the naive implementation is sometimes the correct engineering decision.

O(E + V log V) with a Fibonacci heap, which is asymptotically optimal for comparison-based implementations but rarely faster in practice.

O(V) space for the distance array, the parent array and the visited set, plus the priority queue — which reaches O(E) with lazy deletion rather than O(V).

When to use something else

Unweighted graph? Use BFS. It gives the same answer in O(V + E) with no heap at all, and Dijkstra's extra machinery buys nothing.

Negative weights? Use Bellman-Ford, O(V·E). It relaxes every edge V−1 times and also detects negative cycles, which Dijkstra cannot.

Shortest paths between all pairs? Floyd-Warshall in O(V³) is simpler and often faster than running Dijkstra V times on dense graphs, though V separate Dijkstra runs win on sparse ones.

Single target with a good heuristic? Use A\*, which is Dijkstra with an added estimate of the remaining distance to the goal. Where Dijkstra expands in all directions equally, A\* is pulled towards the target, often exploring a small fraction of the nodes. Provided the heuristic never overestimates — 'admissible' — the result is still optimal. This is what game pathfinding and modern navigation systems actually run.

Continent-scale road networks? Neither, directly. Production routing uses contraction hierarchies and precomputed shortcuts, which answer queries in microseconds by doing hours of preprocessing first. Dijkstra is the foundation they are built on, not the query algorithm.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Dijkstra's Algorithm in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Dijkstra with a binary min-heap and lazy deletion.
 *
 * Lazy deletion: instead of decreasing a key in place (which most heaps do
 * not support), push a new entry and skip stale ones on extraction. The heap
 * can grow to O(E) entries, but the code is far simpler.
 */
class MinHeap {
  constructor() { this.items = []; }

  push(priority, value) {
    this.items.push({ priority, value });
    let i = this.items.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.items[parent].priority <= this.items[i].priority) break;
      [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];
      i = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = last;
      let i = 0;
      for (;;) {
        const left = 2 * i + 1;
        if (left >= this.items.length) break;
        let smallest = left;
        const right = left + 1;
        if (right < this.items.length &&
            this.items[right].priority < this.items[left].priority) {
          smallest = right;
        }
        if (this.items[i].priority <= this.items[smallest].priority) break;
        [this.items[i], this.items[smallest]] =
          [this.items[smallest], this.items[i]];
        i = smallest;
      }
    }
    return top;
  }

  get size() { return this.items.length; }
}

function dijkstra(graph, source) {
  const distance = new Map();
  const parent = new Map();
  const settled = new Set();

  for (const node of graph.keys()) distance.set(node, Infinity);
  distance.set(source, 0);

  const heap = new MinHeap();
  heap.push(0, source);

  while (heap.size > 0) {
    const { value: u } = heap.pop();
    if (settled.has(u)) continue; // stale entry
    settled.add(u);               // distance.get(u) is now final

    for (const [v, weight] of graph.get(u) ?? []) {
      const candidate = distance.get(u) + weight;
      if (candidate < distance.get(v)) {
        distance.set(v, candidate);
        parent.set(v, u);
        heap.push(candidate, v);
      }
    }
  }

  return { distance, parent };
}

const graph = new Map([
  ["A", [["B", 4], ["C", 2]]],
  ["B", [["A", 4], ["C", 1], ["D", 5]]],
  ["C", [["A", 2], ["B", 1], ["D", 8]]],
  ["D", [["B", 5], ["C", 8]]],
]);

console.log([...dijkstra(graph, "A").distance]); // A:0, C:2, B:3, D:8

Advantages and disadvantages

Real-world applications

• GPS navigation and journey planning, where edge weights represent travel time rather than distance.
• Internet routing protocols — OSPF and IS-IS both compute shortest paths with Dijkstra over link costs.
• Game pathfinding, usually as A* with a distance heuristic layered on top.
• Network reliability and latency optimisation, choosing minimum-latency routes through a topology.
• Robot motion planning over weighted terrain grids where different surfaces have different traversal costs.
• Flight and transit itinerary search, minimising total time or price across a network of connections.
• Social network analysis, computing weighted closeness centrality from a node to all others.

Interview questions

The questions that actually get asked about Dijkstra's Algorithm, with the answers an interviewer is listening for.

1. Q1. Why does Dijkstra's algorithm fail with negative edge weights?

   Its correctness rests on the claim that once a node is settled, no cheaper route to it can exist — which holds only because adding more non-negative edges cannot reduce a total. With a negative edge, a path that looks longer at the point of settling can later become cheaper, and since settled nodes are never revisited, that improvement is ignored. The failure is silent: the algorithm returns a plausible wrong answer. Bellman-Ford handles negative weights in O(V·E) and also detects negative cycles.

2. Q2. What is the relationship between BFS, Dijkstra and A*?

   They are the same algorithm with different frontier priorities. BFS takes the node that has been waiting longest, which is correct when all edges cost the same. Dijkstra takes the node with the smallest distance from the source. A* takes the node with the smallest distance-from-source plus estimated-distance-to-goal. Setting all weights to 1 makes Dijkstra behave exactly like BFS; setting A*'s heuristic to zero makes it exactly Dijkstra.

3. Q3. How would you implement Dijkstra when the priority queue has no decrease-key?

   Lazy deletion. When a shorter distance to a node is found, push a new entry rather than updating the existing one, and when popping, skip any entry whose recorded distance is worse than the current best or whose node is already settled. The heap can grow to O(E) entries instead of O(V), but the time complexity is unchanged and the implementation is far simpler — this is what almost all production code does.

4. Q4. When is the O(V²) array implementation better than the heap version?

   On dense graphs where E approaches V². The heap version costs O((V + E) log V), which becomes O(V² log V) when E ≈ V² — worse than V² by a log factor. The array version also has much smaller constants and no allocation. The crossover is roughly when E exceeds V²/log V.

5. Q5. How do you recover the actual path rather than just the distance?

   Record a parent pointer whenever a relaxation succeeds — the node from which the improvement came. When the algorithm finishes, walk backwards from the target through the parent map to the source and reverse. The parent array collectively forms the shortest-path tree, so every target's path is available from one run.

Common mistakes

• Running it on a graph with negative weights and trusting the output, which is wrong without being detectably wrong.
• Using a max-heap instead of a min-heap — in C++ this means forgetting std::greater, which is one of the most common silent bugs in the algorithm.
• Forgetting the stale-entry check after popping, which reprocesses nodes and can produce incorrect results as well as wasted work.
• Marking a node settled when it is first discovered rather than when it is extracted with the minimum distance.
• Using integer maximum as infinity and then adding a weight to it, which overflows to a negative number and corrupts every subsequent comparison.
• Applying Dijkstra to an unweighted graph, where BFS gives the same answer in O(V + E) without any heap.
• Relaxing edges out of already-settled nodes, which wastes time and signals a misunderstanding of what settling means.

Optimisation tips

• Stop as soon as the target node is settled if you only need one destination — the remaining work is pure waste.
• Add an admissible heuristic to get A*, which typically cuts the explored node count by an order of magnitude on spatial graphs.
• Use bidirectional Dijkstra when both endpoints are known, searching from each and meeting in the middle.
• Choose the array implementation for dense graphs and the heap for sparse ones; the crossover is real and measurable.
• Guard against overflow by using a large sentinel rather than the type's maximum, or by checking before adding.
• For repeated queries on a static graph, precompute with contraction hierarchies or landmark-based bounds — this is what production routing engines do, and it turns queries into microsecond lookups.
• For graphs with small integer weights, a bucket queue (Dial's algorithm) beats a binary heap, giving O(E + V·C) where C is the maximum edge weight.

Summary

Dijkstra's algorithm computes shortest paths from a source to every other node in a graph with non-negative weights, by repeatedly settling the nearest unvisited node and relaxing its outgoing edges. The greedy choice is safe precisely because non-negative weights guarantee no shorter route to that node can exist — and that is exactly the assumption a negative edge destroys.

With a binary heap it runs in O((V + E) log V); with a plain array it is O(V²), which is the better choice on dense graphs. It is BFS generalised to weighted edges, and A* is Dijkstra with a heuristic pulling the search towards a goal. If your graph has negative weights use Bellman-Ford; if it is unweighted use BFS; and if it is a continent-scale road network, use something built on top of Dijkstra rather than Dijkstra itself.

Frequently asked questions

Related algorithms

• Breadth-First Search

  Explore a graph level by level with a queue — the shortest path on unweighted edges.

  O(V + E)Intermediate

• Prim's Algorithm

  Grow a minimum spanning tree outward from one node, always taking the cheapest edge out.

  O(E log V)Advanced

• Depth-First Search

  Follow one branch as deep as it goes, then backtrack — a stack, or recursion.

  O(V + E)Intermediate