Visualize how we find the absolute shortest path in a weighted network using a greedy approach.
Graph Config
Search Speed
Search Statistics
Visited Nodes0
Total Nodes0
Weighted Exploration Map
Ready
Click a node to set as Source point • Default is 'A'
Min Priority Queue
PQ is empty
Exploration Path
Dijkstra's always picks the node with the smallest tentative distance. It "relaxes" edges by checking if passing through the current node creates a shorter path to its neighbors.
Overview
On an unweighted graph, BFS finds shortest paths because every edge costs the same and the queue naturally orders nodes by hop count. Add weights and that collapses: a route of three cheap edges can beat one expensive edge. So the fewest hops is no longer the lowest cost.
Why BFS is not enough
Dijkstra’s algorithm fixes this by replacing the queue with a priority queue ordered by distance from the source.
The algorithm, and the invariant that makes it correct
Give the source distance 0 and everything else infinity. Then repeat: take the unvisited node with the smallest tentative distance, mark it visited, and for each neighbour check whether going through this node is cheaper than the neighbour’s current best:
That check is called relaxation. The key claim is that when a node is selected as the minimum, its distance is already final and will never improve.
Why? Any other route to it would have to leave the visited set through some unvisited node w. But w was not chosen, so dist[w] ≥ dist[u], and the rest of that route only adds more weight. So no cheaper route exists. This argument depends entirely on weights being non-negative — “the rest only adds more” is false if a later edge can subtract.
Work one through by hand
Edges: A→B (4), A→C (2), C→B (1), B→D (5), C→D (8), from A.
start: A=0, B=∞, C=∞, D=∞
pick A → relax: B=4, C=2
pick C (2, smallest) → relax: B = min(4, 2+1) = 3, D = 2+8 = 10
pick B (3) → relax: D = min(10, 3+5) = 8
pick D (8) → done
The shortest route to B is A→C→B at cost 3, not the direct edge at cost 4. Two hops beat one, which is exactly the case BFS gets wrong.
Complexity, and what the heap buys
Priority queue
Complexity
Unsorted array scan
O(V²)
Binary heap
O((V + E) log V)
Fibonacci heap
O(E + V log V) — theoretical
The binary heap version is what everyone uses. Fibonacci heaps are asymptotically better and their constant factors are poor enough that they lose in practice.
The O(V²) array version is faster on dense graphs, where E approaches V², because it avoids the heap overhead. That is a real consideration for complete or near-complete graphs.
To recover the path rather than just the distances, record each node's predecessor when its distance is improved, and walk backwards from the goal.
Exploration guide
Watch it expand by cost, not by distance on screen. Press Start Solver then Step repeatedly. The next node chosen is always the cheapest known, which is often not the nearest-looking one.
Catch a relaxation. Keep stepping and watch a node’s distance drop when a better route is found. Every improvement is one relaxation, and once a node is finalised its number never changes again.
Traps worth knowing
Using it with negative edge weights. The correctness argument fails and the algorithm returns wrong answers silently. A node finalised early may have a cheaper route through an edge considered later. Use Bellman-Ford, which handles negatives in O(VE) and detects negative cycles.
Re-processing stale heap entries. Most implementations push duplicates instead of doing decrease-key. You must skip a popped node if it is already visited, or you will relax from an out-of-date distance.
Forgetting the predecessor array. Dijkstra computes distances; reconstructing the actual route needs the parent pointer recorded on every successful relaxation.
Running it to completion when one target is wanted. You can stop as soon as the target is popped. Its distance is final at that moment. Continuing wastes the rest of the graph.
Where it is used
Route planning. Every navigation system is Dijkstra or a derivative, with edge weights as travel time.
Network routing. OSPF, a core internet routing protocol, runs Dijkstra over link costs.
Flight and journey planning with cost, duration or number of changes as weights.
Game pathfinding — usually A*, which is Dijkstra plus a heuristic.
Dependency resolution with weighted preferences.
Image processing — seam carving and intelligent scissors find minimum-cost paths through a pixel grid.
Real navigation systems do not run plain Dijkstra over a continental road network for every query — that would be too slow. They use precomputation: contraction hierarchies, which shortcut through unimportant nodes, or A* with a landmark-based heuristic. The underlying algorithm is still this one.
Continue with Bellman–Ford, which builds on this idea.
Run it in Python
A priority queue, a distance table, and a printout of every pop and every relaxation. The second half feeds it a negative edge to show the exact point at which the algorithm is wrong.
dijkstra.pyPython 3
# Dijkstra: always finalise the nearest unfinished node.
import heapq
graph = {
"A": {"B": 4, "C": 2},
"B": {"C": 5, "D": 10},
"C": {"E": 3},
"D": {"F": 11},
"E": {"D": 4},
"F": {},
}
def dijkstra(graph, start):
dist = {n: float("inf") for n in graph}
dist[start] = 0
parent = {start: None}
done = set()
heap = [(0, start)] # (distance so far, node)
while heap:
d, node = heapq.heappop(heap) # the nearest unfinished node
if node in done:
continue # a stale copy; skip it
done.add(node)
print(f"finalise {node} at {d}")
for neighbour, weight in graph[node].items():
if d + weight < dist[neighbour]:
dist[neighbour] = d + weight
parent[neighbour] = node
heapq.heappush(heap, (dist[neighbour], neighbour))
print(f" relax {node}->{neighbour}: {dist[neighbour]}")
return dist, parent
dist, parent = dijkstra(graph, "A")
print()
print("distances:", dist)
path, node = [], "F"
while node is not None:
path.append(node)
node = parent[node]
print("A -> F :", " -> ".join(reversed(path)), "=", dist["F"])
print()
print("Now with a negative edge (B -> C costs -6):")
graph["B"]["C"] = -6
bad, _ = dijkstra(graph, "A")
print("distances:", bad)
print("A->B->C is 4 + -6 = -2, but C was finalised at 2 and never revisited.")
Output
How the code works
heap = [(0, start)]Tuples, so the heap orders by distance first. Python's heapq is a min-heap over whatever you give it, and putting the distance first is what makes it a priority queue over distances.
if node in done: continueThe lazy-deletion trick. heapq cannot update a key in place, so improved distances are pushed as new entries and the stale ones are skipped when they surface. Cheaper than a decrease-key structure, and far easier to get right.
if d + weight < dist[neighbour]:The relaxation, and the whole algorithm. “I have a route to node that costs d; going on to neighbour beats whatever I had.”
done.add(node)The node's distance is now final and will never be improved. This is the claim the correctness proof rests on — and it holds only because every edge is non-negative, so no later route can be shorter.
graph["B"]["C"] = -6The counterexample. C is finalised at 2 before B is even examined, so the cheaper route through B arrives too late. Dijkstra does not detect this; it just returns a wrong answer. Use Bellman-Ford instead.
Change one thing
Set graph["A"]["C"] = 20. The finalisation order changes and the path to F reroutes — watch the relax lines that get superseded.
Print len(heap) each iteration. It exceeds the node count, which is the stale entries lazy deletion leaves behind.
Replace the heap with a linear scan for the nearest unfinished node. The answers are identical and the complexity goes from O(E log V) to O(V²).
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Watch it expand by cost, not by distance on screen. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
With one negative edge, Dijkstra:
The program finalises C at 2, then discovers a route through B worth -2 and never revisits it. Correctness rests on no edge ever making a finalised node cheaper.
Why does the code push a new heap entry instead of updating an existing one?
Lazy deletion: cheaper and far easier to get right than a decrease-key structure, at the cost of a heap larger than the node count.
Replacing the heap with a linear scan for the nearest node gives:
The heap is an accelerator, not part of the logic. On a dense graph the O(V²) version is actually competitive.
Cheat sheet
Dijkstra's Algorithm
Watch Dijkstra's algorithm settle nodes in order of distance and build the shortest path across a weighted graph.
A Note on Two Problems in Connexion with GraphsDijkstra, Numerische Mathematik 1959
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.