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:
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.
- 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] = ∞.
- 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).
- 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).
- 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 routes0 → 1 → 3(cost 5) and0 → 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:
- Set the Nodes slider to
6for a compact graph where every edge weight and tentative distance labeld=...is easy to inspect. - Click Step once to initialize source vertex
0(green) atd=0, then click Step again and predict which blue queued neighbor has the minimum tentative distance before it turns purple as the current vertex. - Continue clicking Step (or click Run) until the algorithm finishes. Compare the amber highlighted shortest path against the
Shortest pathandTotal weightvalues in the Status panel. - 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:
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Demaine, E., Ku, J., & Solomon, J. MIT 6.006 Introduction to Algorithms, Lecture 13: Dijkstra's Algorithm. MIT OpenCourseWare. MIT 6.006 Lecture 13 Notes (PDF)
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 →