Dijkstra's algorithm
Find shortest paths when every edge has a non-negative weight by repeatedly locking in the nearest unsettled vertex.
Big idea
How it thinks about the graph
Keep a tentative distance to every vertex. At each step, choose the unsettled vertex with the smallest tentative distance and relax its outgoing edges.
Useful when
Road networks, routing, weighted maps and situations where costs are never negative.
Watch out: Dijkstra's algorithm is not reliable with negative edge weights because a later negative edge could improve a path that was already treated as final.
Questions to investigate
Which tentative distance should become permanent next?
Why do non-negative weights matter?
How does the algorithm know it has found the shortest path?
Open the interactive explorer
This algorithm already has a working prototype. Use it to build a graph, make a prediction, then step through the search.
Open Dijkstra's algorithm explorer