ƒ(x) GraphAdvanced interactive
Dijkstra's Shortest Path
Greedy shortest paths with a priority queue.
graph_dijkstra
step 1 / 16
dist[A] = 0, all others ∞.
in queuecurrentvisitedshortest path
speed1×
How it works
Dijkstra's algorithm finds the shortest path from a source to every node in a weighted graph with non-negative edges. It greedily settles the closest unvisited node, relaxing its neighbors, using a min-heap to always pick the nearest frontier vertex.
Mental models
- Relaxation: if dist[u] + w < dist[v], you found a shorter route.
- Once a node is settled, its distance is final — that's the greedy step.
Common pitfalls
- Fails with negative edges — use Bellman-Ford instead.
Complexity
- Time
- O((V + E) log V)binary heap
- Space
- O(V)
Reach for it when
- GPS routing
- Network latency
- Game pathfinding