Visualize how we find the absolute shortest path in a weighted network using a greedy approach.
Overview
Why BFS is not enough
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.
Dijkstra’s algorithm fixes this by replacing the queue with a priority queue ordered by distance from the source. Instead of expanding the node discovered earliest, it expands the node whose known distance is smallest.
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.
Dijkstra's Algorithm: A Practical Guide
Grow a set of nodes whose shortest distance is already final, always expanding the cheapest one next. It is the standard weighted shortest-path algorithm, and it breaks the moment an edge weight goes negative.
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.
Shortest paths when edges have weights
BFS finds the path with the fewest edges. Dijkstra's algorithm finds the path with the lowest total cost, which is a different thing whenever edges differ in weight.
A three-edge route along quiet roads can be faster than a one-edge route along a jammed motorway. BFS would pick the motorway; Dijkstra picks correctly.
The algorithm is BFS with a priority queue instead of a plain queue:
Set the start's distance to 0 and every other to infinity.
Take the unvisited node with the smallest known distance.
For each neighbour, if going through this node is cheaper than its current best, update it.
Mark the node finished and repeat.
import heapq
def dijkstra(graph, start):
dist = {start: 0}
pq = [(0, start)] # (distance, node)
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float("inf")):
continue # a stale entry - skip it
for nbr, weight in graph[node]:
nd = d + weight
if nd < dist.get(nbr, float("inf")):
dist[nbr] = nd
heapq.heappush(pq, (nd, nbr))
return dist
The continue on line 8 is the detail that matters. Python's heapq has no decrease-key operation, so an improved distance is pushed as a new entry rather than updating the old one. The old entry is still in the heap, and skipping it when popped is what keeps the algorithm correct. This is called lazy deletion, and omitting the check produces subtly wrong results.
Why it needs non-negative weights
The algorithm's correctness rests on one claim: once a node is popped with the smallest tentative distance, that distance is final.
That holds because every edge adds a non-negative amount, so no path discovered later can be shorter. Any route to that node through an unvisited node would already be at least as long.
With a negative edge, the claim collapses. A node finalised at distance 5 might later be reachable at distance 2 via a negative edge from a node not yet processed — and Dijkstra never revisits it.
Situation
Algorithm
Unweighted
BFS — O(V+E)
Non-negative weights
Dijkstra — O((V+E) log V)
Negative weights
Bellman-Ford — O(VE)
Negative cycles
Bellman-Ford, which detects them
All pairs
Floyd-Warshall — O(V³)
With a heuristic
A* — Dijkstra guided towards the goal
Negative weights are not exotic: currency arbitrage, energy gained rather than spent, and rebates all produce them. Knowing that Dijkstra silently gives wrong answers there — rather than failing — is the practically important point.
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.
Slow the expansion. Set Search Speed to 1 and press Auto. The visited set grows outward in rings of equal cost — that shape is Dijkstra exploring uniformly in every direction, which is precisely what A* improves on.
Change the graph. Pick a different Network Topology, press Reset Grid, and run again. On a denser graph many more relaxations happen per node, because each node has more neighbours to improve.
Complexity, and why the priority queue matters
With a binary heap the cost is O((V + E) log V): each of V nodes is extracted once at O(log V), and each of E edges may trigger a decrease-key at O(log V).
With a naive array scan for the minimum it is O(V²), which is actually faster on dense graphs where E approaches V². With a Fibonacci heap the theoretical bound improves to O(E + V log V), though the constants are bad enough that binary heaps usually win in practice.
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.
In one line
Dijkstra’s algorithm repeatedly finalises the cheapest unvisited node and relaxes its edges, giving single-source shortest paths in O((V + E) log V) with a binary heap. Its correctness rests on non-negative weights, so negative edges call for Bellman-Ford instead. Because it expands uniformly in all directions, it does more work than necessary when you only want one destination — which is the gap A* fills.
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.
A*: the same algorithm with a hint
A* changes one thing. Instead of prioritising by distance from the start, it prioritises by
f(n) = g(n) + h(n)
where g is the known distance from the start and h is an estimate of the remaining distance to the goal.
That estimate focuses the search towards the goal rather than expanding uniformly in all directions, which on a large map is dramatically fewer nodes explored.
The condition for correctness is that h must be admissible — never overestimating the true remaining cost. Straight-line distance is admissible for road networks, because no road is shorter than the straight line.
With h = 0, A* is Dijkstra. With an overly optimistic heuristic it explores more; with an inadmissible one it may return a suboptimal path quickly, which is sometimes an acceptable trade.
Common mistakes
Using it with negative weights. No error, wrong answer. Use Bellman-Ford.
Forgetting the stale-entry check when using a heap without decrease-key.
Marking nodes visited on push rather than on pop. A node's distance can improve while it sits in the queue.
Confusing it with BFS on an unweighted graph. Dijkstra works there and BFS is simpler and faster.
Comparing nodes in the heap. If distances tie, Python compares the second tuple element — so nodes must be comparable, or push a tiebreaking counter.
Running it for a single target and not stopping. Break when the goal is popped; continuing computes distances you do not need.
Why it needs non-negative weights, on a graph where it fails
Every description of Dijkstra's algorithm mentions that edge weights must be non-negative. It is more convincing to build the graph that breaks it and watch the algorithm return a wrong answer confidently, because the failure is silent -- there is no error, just a shorter path it never looks at again.
example_01.pyPython
import heapq
# Positive weights: the algorithm is correct here.
GOOD = {
"A": [("B", 1), ("C", 4)],
"B": [("C", 2), ("D", 6)],
"C": [("D", 3)],
"D": [],
}
def dijkstra(graph, start):
dist = {n: float("inf") for n in graph}
dist[start] = 0
settled, order = set(), []
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if node in settled:
continue
settled.add(node)
order.append((node, d))
for nxt, w in graph[node]:
if d + w < dist[nxt]:
dist[nxt] = d + w
heapq.heappush(pq, (dist[nxt], nxt))
return dist, order
dist, order = dijkstra(GOOD, "A")
print("settling order (node, distance when settled):")
for node, d in order:
print(" %s at %d" % (node, d))
print("final distances:", dict(dist))
# Note A=0, B=1, C=3, D=6 -- and note C was settled at 3 via B, not at 4
# via the direct edge. The queue handed back the cheaper route first.
#
# The invariant doing the work: when a node comes off the priority queue,
# its distance is FINAL. That holds because every remaining path to it
# must go through some unsettled node that is already at least as far
# away, and adding more non-negative edges can only make it longer.
#
# Remove the non-negative part and the invariant collapses.
BAD = {
"A": [("B", 2), ("C", 5)],
"B": [("D", 3)],
"C": [("B", -4)], # a negative edge
"D": [],
}
dist, order = dijkstra(BAD, "A")
print()
print("with a -4 edge, settling order:")
for node, d in order:
print(" %s at %d" % (node, d))
print("Dijkstra says A -> D costs", dist["D"])
# It settled B at 2 and moved on. Later it reached C at 5, and C offers
# B at 5 + (-4) = 1 -- cheaper than the 2 it committed to. B was already
# settled, so the improvement is never propagated to D.
print()
print("the route it never considered: A -> C -> B -> D = %d + %d + %d = %d"
% (5, -4, 3, 5 - 4 + 3))
print("the answer it gave: ", dist["D"])
# The real shortest path costs four; the algorithm reported five, with no
# warning of any kind and no way for the caller to tell. This is the exact
# situation Bellman-Ford exists for: it relaxes every edge V-1 times
# rather than settling nodes once, so a late improvement still propagates.
#
# Finally, what the heap actually buys. Without one you scan every
# unsettled node to find the nearest:
import math
print()
print("%10s %16s %20s" % ("V (E = 5V)", "array O(V^2)", "binary heap O(E log V)"))
for v in (10, 100, 1000, 10000):
e = 5 * v
print("%10d %16d %20d" % (v, v * v, int(e * math.log2(v))))
# Read the first row: at ten nodes the heap is the SLOWER option, because
# log V is not yet worth the bookkeeping. By a thousand nodes the array
# costs twenty times more, and by ten thousand, a hundred and fifty times.
# That is the usual shape of an asymptotic win -- it arrives at a size,
# not immediately. On a dense graph where E approaches V^2 the array
# version stays competitive at any size, which is why both are still
# taught.
Output
Questions people ask
Why not BFS on a weighted graph? BFS minimises edge count, not cost. Three cheap edges can beat one expensive one.
What if weights are all equal? Use BFS — O(V+E) without the log factor.
How do I get the actual path? Store a predecessor for each node whenever its distance improves, then walk back from the goal.
Can I stop early? Yes — when the target is popped, its distance is final. Everything after that is unnecessary work.
Does it work on directed graphs? Yes, unchanged. Only follow outgoing edges.
What about several sources? Push all sources with distance 0. The result is each node's distance to the nearest source, in one run.
Recap in one screen
Dijkstra is BFS with a priority queue: always expand the closest unfinished node.
Its correctness depends on non-negative weights — with negatives it is silently wrong, so use Bellman-Ford.
Use lazy deletion with heapq: push improved distances and skip stale entries when popped.
O((V+E) log V) with a binary heap; the O(V²) array version wins on dense graphs.
A* is the same algorithm prioritised by distance-so-far plus an admissible estimate of what remains.
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.
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
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.
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.