History
Edsger W. Dijkstra designed the algorithm in 1956 while thinking about the shortest route between two cities. He published it in 1959. Its compact greedy idea became a foundation of graph theory and route-planning software.
Graph algorithms / interactive lesson
Dijkstra's Shortest Path Algorithm
Discover the shortest routes from one source. Watch tentative distances improve through relaxation, see nodes become final in priority order, and inspect the resulting predecessor tree.
High School
Guided lesson
Snapshot 1/17
Shortest-path graph · cyan inspection · orange relaxation · green predecessor tree
Decision timeline
Set A as the source
About the algorithm
Dijkstra's algorithm finds the shortest route from one source vertex to every reachable vertex in a weighted graph. It records the best distance discovered so far, repeatedly finalizes the closest unsettled vertex, and improves its neighbors through relaxation.
How it works
Start with distance 0 at the source and infinity elsewhere. Select the unsettled vertex with the smallest tentative distance. For each neighbor, test whether traveling through the selected vertex creates a cheaper route. This update is called relaxation.
Where it is used
Dijkstra's algorithm supports route planning, network routing, map navigation, robot movement, game pathfinding, and dependency analysis. It requires non-negative edge weights; graphs with negative costs need a different algorithm.
Code companion
Connect each visual decision to an implementation pattern.
distance[source] = 0
distance[other nodes] = infinity
while unsettled reachable nodes remain:
current = unsettled node with minimum distance
settle current
for each unsettled neighbor of current:
candidate = distance[current] + edge.weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
predecessor[neighbor] = current
return distance, predecessor