Dijkstra's Algorithm Visualizer

How it works

1. Set dist[s] = 0 and every other dist[v] = ∞, and push (0, s) into a min-priority queue.
2. Pop the entry with the smallest distance. If its node u is already finalized, the entry is stale — skip it.
3. Finalize u: its distance can no longer improve.
4. Relax each edge u → v with weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w, parent[v] = u and push (dist[v], v).
5. Repeat until the queue is empty, then follow parent pointers back from any node to read its shortest path.

Why the greedy choice is safe

Suppose u is the unfinished node with the smallest tentative distance d. Any other route to u has to leave the finalized set through some unfinished node x, and dist[x] ≥ d because u was the smallest. Every edge after that adds a non-negative amount, so the detour costs at least d. Therefore d is final, and Dijkstra never has to revisit a node.

That one sentence — "edges can only add" — is the whole proof, and it is exactly what breaks when an edge is negative. It also shows how Dijkstra generalizes BFS: when every weight is 1, nodes come out of the priority queue in the same order a FIFO queue would produce.

Worked example

The page opens on a 7-node undirected graph: A–B 4, A–C 2, B–C 1, B–D 5, B–E 9, C–D 8, C–F 10, D–E 3, D–F 2, E–G 1, F–G 6. From A:

• Finalize A (0): B = 4, C = 2.
• Finalize C (2): B improves from 4 to 3 through C; D = 10, F = 12.
• Finalize B (3): D improves from 10 to 8; E = 12.
• Finalize D (8): E improves from 12 to 11 and F from 12 to 10.
• Finalize F (10): G = 16. Finalize E (11): G improves to 12. Finalize G (12).

Final distances: A 0, B 3, C 2, D 8, E 11, F 10, G 12. The cheapest route to G is A → C → B → D → E → G — five edges — while the three-edge route A → B → E → G costs 14. Fewest edges is not cheapest, which is precisely why BFS is not enough for weighted graphs.

Why Dijkstra fails with negative weights

Take the directed graph A → B 2, A → C 5, C → B −4, B → D 3, D → E 1, C → E 8 (the Negative edge demo preset). Dijkstra finalizes B at distance 2 before it ever expands C, so the cheaper route A → C → B (5 − 4 = 1) arrives too late; D and E inherit the error and come out as 5 and 6 instead of 4 and 5. Bellman-Ford gets all of them right.

Adding a constant to every weight to make them positive does not help: it penalizes paths with more edges, so the shortest path can change. Johnson's algorithm reweights correctly using potentials computed by Bellman-Ford, and on a DAG you can relax edges in topological order, which handles negative weights in O(V + E).

Implementation choices

• Binary heap with lazy deletion (the code below): push a new entry whenever a distance improves and skip stale entries when they are popped. O((V + E) log V) time; the heap can hold up to E entries.
• Indexed heap with decrease-key: the same time bound with at most V entries, at the cost of more code.
• Plain array: scan all nodes for the minimum each round — O(V²) total, which beats a heap on dense graphs where E ≈ V².
• Fibonacci heap: O(E + V log V) in theory, rarely faster in practice.
• Single target: stop as soon as the target is popped; A* goes further by adding a distance estimate to the key.

Common mistakes and where it is used

• Finalizing a node when it is pushed rather than when it is popped — the first distance found is often not the shortest (B was first reached at 4, but its real distance is 3).
• Not skipping stale heap entries, so finalized nodes are expanded again.
• Overflow in C++ or Java when computing INF + w; guard unreachable nodes or use a large-but-safe infinity.
• Running it on negative weights and trusting the result.

Dijkstra (often with A* or contraction hierarchies on top) is behind road navigation, link-state routing protocols such as OSPF and IS-IS, and game path-finding. Interview favourites include network delay time, path with minimum effort, and swim in rising water, where grid cells are the nodes.

Time and space complexity

Dijkstra's Algorithm in Python

import heapq
import math


def dijkstra(graph, s):
    """graph: {node: [(neighbour, weight)]}, weights >= 0.
    Returns dist (math.inf = unreachable)."""
    dist = {v: math.inf for v in graph}
    dist[s] = 0
    finalized = set()
    pq = [(0, s)]                          # min-heap of (dist, node)
    while pq:
        _, u = heapq.heappop(pq)           # u <- PQ.extractMin()
        if u in finalized:
            continue                       # stale entry: u is already final
        finalized.add(u)
        for v, w in graph[u]:              # each edge (u, v, w)
            if v in finalized:
                continue                   # v is final: skip
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))  # PQ.update: push the smaller key
    return dist

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Bellman-Ford Algorithm VisualizerBellman-Ford finds shortest paths even with negative edge weights and detects negative cycles. Watch each relaxation pass step by step, with O(V·E) code.
• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• Prim's Algorithm VisualizerPrim's algorithm grows a minimum spanning tree from one node by always adding the cheapest edge leaving the tree. Watch it step by step, with heap-based code.
• Priority Queue VisualizerPriority queue visualizer: a binary heap always serves the top-priority item first. Watch insert, peek and extract in O(log n) and see how Dijkstra uses it.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.