Interactive step-by-step visualization — watch the priority queue, distance table, and edge relaxation in real time
Shortest paths from a source node — step by step with priority queue
Press "Run Dijkstra's" to start
empty
1. Initialize
dist[start] = 0, all others = ∞. Push (0, start) to the min-heap.
2. Pop minimum
Pull the unvisited node with the smallest tentative distance.
3. Relax edges
For each neighbor v: if dist[u] + w < dist[v], update dist[v] and push to heap.
4. Settle
Mark the node visited — its distance is now final. Repeat until the heap is empty.
All edge weights are non-negative. When we pop a node, its tentative distance is already the shortest possible — no future relaxation through other nodes (which have equal or larger distances) can improve it. This greedy argument guarantees correctness.
Python: use heapq.heappush / heapq.heappop for an O(log V) priority queue. The algorithm runs in O((V + E) log V).
| Operation | Complexity | Why |
|---|---|---|
| Time (binary heap) | O((V+E) log V) | Each edge triggers at most one heap push (O(log V)) |
| Space | O(V + E) | Adjacency list + dist array + heap |