Medium · Dijkstra's Algorithm
Understand → Visualise → Practice.
With non-negative edge weights, the smallest tentative distance in a priority queue can never be improved by travelling through a farther vertex.
Pop the smallest distance, skip stale entries, and relax every outgoing edge.
source distance 0; all others infinity.
The heap gives the nearest candidate.
If dist[u] + weight improves v, update and push it.
O((V + E) log V) time and O(V + E) space with adjacency lists and a binary heap.
Dijkstra is not correct with negative edge weights; use Bellman–Ford for those graphs.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.