Dijkstra's Shortest Path

Watch Dijkstra's algorithm find the shortest path in a weighted graph.

Worked example — Dijkstra's Shortest Path

Node 0	0
Node 1	3
Node 2	8
Node 3	2
Node 4	8
Shortest path	0 → 3 → 4 (cost: 8)

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Relaxation is the whole algorithm; the priority queue is only speed 🖖

Dijkstra's algorithm finds the shortest path between nodes in a graph with non-negative edge weights. It operates greedily, maintaining a set of visited nodes and updating distance estimates using the relaxation step: d(v) = min(d(v), d(u) + w(u,v)). The time complexity is optimized to O(E + V log V) using a Fibonacci heap priority queue, demonstrating how structured data layout prevents redundant path searches.

Why the nearest node is always safe 🖖

Dijkstra grows a frontier outward from the start, always settling the unvisited node that is currently closest. Because every edge weight is non-negative, no later detour can ever beat a shorter route already found — so once a node is settled, its distance is final and never revisited. That is why route planners and internet routing protocols like OSPF rely on it to compute reliable shortest paths.

Invented in twenty minutes over coffee 🖖

Edsger Dijkstra conceived the algorithm in 1956 in about twenty minutes, with no pencil or paper, while resting at an Amsterdam café terrace. He was hunting for a demonstration problem for the ARMAC computer and chose the shortest route between two Dutch cities, Rotterdam and Groningen. He published it three years later in a paper barely three pages long — one of computing's most cited results.

Problem solved in full

Node 1 one edge from the source at a cost of 4 5 steps
Node 1 is one edge from the source, at a cost of 4 — and the algorithm reports its distance as 3. Work through the settling order and find where the 3 comes from.
1. Dijkstra settles nodes in order of distance, never revisiting. That ordering is the whole algorithm and the whole proof: when a node is settled, no cheaper route to it can exist, because any such route would have to pass through an unsettled node that is already further away.
  
  $E = {(0, 1, 4), (0, 3, 2), (1, 2, 5), (1, 3, 1), (2, 4, 3), (3, 4, 6)}$
2. From the source the two direct edges give tentative distances of 4 and 2. Neither is final yet — they are upper bounds.
  
  $settle 0 : d_{1} = 4, d_{3} = 2$
3. The nearest is node 3 at 2, so it settles first. Relaxing its edges finds a route to node 1 costing 2 + 1 = 3, which beats the direct edge of 4. This is the step that answers the question: the cheapest way to a neighbour need not be the edge to it.
  
  $settle 3 (d = 2) : d_{1} = min (4, 2 + 1) = 3, d_{4} = 2 + 6 = 8$
4. Node 1 settles at 3, and relaxing from there reaches node 2 at 8.
  
  $settle 1 (d = 3) : d_{2} = 3 + 5 = 8$
5. Node 4 is reachable at 8 through node 3, and the alternative through node 2 costs 8 + 3 = 11, so the shorter one stands.
  
  $settle 2, 4 : d_{4} = min (8, 8 + 3) = 8 ⟹ 0 \to 3 \to 4$
Answer

The tool prints distances of 3, 8, 2, 8 and a shortest path of 0 → 3 → 4. The lesson is in node 1: a direct edge is not a shortest path, and greedy settling is what makes finding that out cheap rather than exponential. The guarantee has one requirement, though — non-negative weights. With a negative edge, a node settled early can later be improved, and the proof in step 1 collapses. Click the negative-edge preset and watch it fail in both directions at once: node 3 comes back at −1, which is not a distance any route produces, and the path reconstruction gives up entirely with “no path — the predecessors form a loop”. Wrong numbers and no route, from an algorithm that is provably correct the moment every weight is non-negative.

$d_{1} = 3 via node 3, not 4 direct; 0 \to 3 \to 4 = 8$

References (2)

The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.

By the 42Math team · Updated 2026-06-11

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

5-node city - 5-node city: shortest path 0→4
3×3 grid - 3×3 grid: multiple shortest paths
Deep vs broad - Deep vs broad: greedy fails
Negative edge - Negative edge: Dijkstra may fail