Computer Science

Dijkstra's Algorithm

Finding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.

By Riano · Published · Updated · Report a correction

Dijkstra's Algorithm

Concept Overview

Dijkstra's algorithm computes shortest-path distances from a source vertex s to all vertices in a graph with non-negative edge weights. By repeatedly extracting the unvisited vertex u with the smallest tentative distance d[u] and relaxing its outgoing edges, the algorithm maintains the invariant that every settled vertex has achieved its true minimum path cost.

Mathematical Definition

Given a weighted graph G = (V, E) with weight function w : E → ℝ≥0 and source s ∈ V:

1. Initialize d[s] = 0, d[v] = ∞ for all v ≠ s, and unsettled set Q = V.
2. While Q is non-empty:
Extract u = argminv ∈ Q d[v].
For each neighbor v of u with v ∈ Q:
if d[u] + w(u, v) < d[v] then d[v] ← d[u] + w(u, v) and prev[v] ← u.

Worked Example: Why Fewest Edges Is Not Always Shortest

Consider a 4-vertex undirected graph with source 0, target 3, and five weighted edges: (0, 1) = 4, (0, 2) = 1, (2, 1) = 2, (1, 3) = 1, and (2, 3) = 5.

  1. Step 1 (settle 0 at d[0] = 0): Relaxing neighbors of 0 sets d[1] = 4 (via 0) and d[2] = 1 (via 0), while d[3] = ∞.
  2. Step 2 (settle 2 at d[2] = 1): Vertex 2 has the smallest tentative distance (1 < 4). Relaxing edge (2, 1) checks 1 + 2 = 3 < 4, lowering d[1] from 4 to 3 (via 2). Relaxing edge (2, 3) sets d[3] = 1 + 5 = 6 (via 2).
  3. Step 3 (settle 1 at d[1] = 3): Vertex 1 is extracted next (3 < 6). Relaxing edge (1, 3) checks 3 + 1 = 4 < 6, lowering d[3] from 6 to 4 (via 1).
  4. Step 4 (settle 3 at d[3] = 4): The target is settled with optimal distance 4 along the 3-edge route 0 → 2 → 1 → 3 (cost 1 + 2 + 1 = 4), beating both 2-edge routes 0 → 1 → 3 (cost 5) and 0 → 2 → 3 (cost 6).

Interactive Experiment: What to Enter and Observe

Open the Dijkstra's Algorithm module to step through vertex extraction and edge relaxation:

  1. Set the Nodes slider to 6 for a compact graph where every edge weight and tentative distance label d=... is easy to inspect.
  2. Click Step once to initialize source vertex 0 (green) at d=0, then click Step again and predict which blue queued neighbor has the minimum tentative distance before it turns purple as the current vertex.
  3. Continue clicking Step (or click Run) until the algorithm finishes. Compare the amber highlighted shortest path against the Shortest path and Total weight values in the Status panel.
  4. Click a different node on the canvas to reassign the red Target (or Shift+click to change the green Source), then press Run to see how the shortest path tree adapts on the same weighted graph.

Assumptions & Limitations

Dijkstra's greedy settlement invariant requires non-negative edge weights (w(u, v) ≥ 0). If a directed graph has edges 0 → 1 of weight 2, 0 → 2 of weight 5, and 2 → 1 of weight −10, settling vertex 1 first at d[1] = 2 misses the cheaper path 0 → 2 → 1 of total weight −5; graphs with negative weights require the Bellman–Ford algorithm. In addition, visual Euclidean distance on the canvas does not determine path cost—only the numerical edge weight labels enter the relaxation sum d[u] + w(u, v).

References

Dijkstra published his shortest-path construction in 1959, and MIT 6.006 Lecture 13 covers the correctness proof via the non-negative relaxation invariant and priority-queue complexity:

Experience it interactively

Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Dijkstra's Algorithm module.

Try Dijkstra's Algorithm on Riano →

More in Computer Science