Dijkstra's Algorithm
Finding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.
Free theory articleFinding the shortest path in a weighted graph by greedily exploring the nearest unvisited node.
Concept & interpretation
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.
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.