DSA · interactive
Dijkstra: shortest paths
Find the cheapest route from A to every other node. Always settle the closest node you haven't settled yet, then see whether going through it makes its neighbours cheaper. Weights must not be negative.
Queue (closest first): A:0
Distance to A is 0; everything else is ∞. Always settle the closest unsettled node next.
step 1 of 17
1 Distance 0 to the start, unknown (∞) to everything else. Put the start in a priority queue.
The number under each node is its best known distance.
2 3 4
Now solve it
Advanced Graphs: 5 problems
See all →In production
Tools and technologies
Shortest-path search runs maps and networks.
Not tied to one language — use these names when you search docs or design a system.