Dijkstra's Algorithm —
Greedily expand the cheapest known path.
Dijkstra finds the shortest path in a weighted graph by always expanding the unvisited node with the smallest known distance so far — a priority queue keeps that decision O(log n) instead of a linear scan. Watch the distance table update and the priority queue pop nodes in cost order on LearnBug, and see why a shorter path found later can still update an already-visited value.
What is Dijkstra's Algorithm?
Track the best known distance from the start to every node, starting at 0 for the start and infinity everywhere else. Repeatedly pop the unvisited node with the smallest known distance, and for each of its edges, check whether going through this node gives a shorter path to the neighbor than what's currently known — if so, update it.
Why visualization helps
The greedy choice — always process the cheapest frontier node next — is what guarantees correctness, but it's easy to lose track of why a node's distance changes mid-algorithm. LearnBug shows the full distance table updating live and highlights exactly which edge triggered each improvement, so "relaxing an edge" stops being an abstract term.
What makes Dijkstra different from BFS
Edge weights matter
BFS assumes every edge costs 1 — Dijkstra handles different costs per edge, so "fewest hops" and "cheapest path" can disagree.
Greedy + priority queue
Always expanding the cheapest known frontier node — via a min-heap — guarantees that once a node is popped, its distance is final.
Breaks with negative weights
The greedy guarantee relies on weights being non-negative — a later negative edge could undercut an already-finalized distance.
Dijkstra from A — A→B(4), A→C(1), C→B(2), B→D(5), C→D(8)
Start: dist[A]=0, everything else infinity — pop A first
A's two edges relax B and C: dist[B] = 0+4 = 4, dist[C] = 0+1 = 1. Both get pushed onto the priority queue with their new distances.
Pop C (distance 1, the smallest) — relax B and D through C
Going A→C→B costs 1+2=3, which beats the current dist[B]=4 — update it. Going A→C→D costs 1+8=9, better than infinity — update dist[D].
Pop B (distance 3, the new smallest) — relax D through B
Going A→C→B→D costs 3+5=8, which beats the current dist[D]=9 — update it again. The stale queue entry (4, B) will simply be skipped when it's popped later, since 4 > the now-finalized dist[B]=3.
Pop D (distance 8) — no outgoing edges, queue drains, done
D has no neighbors to relax. The remaining stale entries (4, B) and (9, D) get popped and immediately discarded because they no longer match the finalized distances.
Final: A=0, C=1, B=3, D=8 ✓ shortest path to D is A → C → B → D, cost 8
Dijkstra with a min-heap
import heapq
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 5)],
"C": [("B", 2), ("D", 8)],
"D": [],
}
def dijkstra(start):
dist = {node: float("inf") for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue # stale entry — a shorter path already won
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist # relax the edge
heapq.heappush(heap, (new_dist, neighbor))
return distComplexity Notes
Frequently asked questions
Why doesn't Dijkstra work with negative edge weights?
Dijkstra assumes that once a node is popped with its minimum distance, that distance can never improve — because every remaining path must add non-negative weight. A negative edge can violate that assumption, letting a later path undercut an already-finalized distance. Bellman-Ford handles negative weights correctly (at higher time cost) instead.
What are those "stale" heap entries about?
Since a node's distance can be updated multiple times before it's finalized, the same node can end up pushed onto the heap more than once, each with a different distance. Rather than removing the old entry (expensive with a heap), the algorithm just checks if d > dist[node]: continue and skips it when popped.
How is Dijkstra related to BFS?
BFS is Dijkstra's algorithm with every edge weight fixed at 1 — the priority queue degenerates into a plain FIFO queue because "smallest distance so far" always matches "fewest edges so far." That's why BFS is enough for unweighted shortest paths and Dijkstra is only needed when weights vary.
What's the difference between Dijkstra and A*?
A* is Dijkstra plus a heuristic function that estimates remaining distance to a specific target, letting it prioritize promising nodes and often finish faster. Dijkstra with no target has to explore fully outward in every direction; A* is only useful when you have one specific destination and a good heuristic (e.g. straight-line distance on a map).
Watch the distance table update as the queue pops nodes
Paste your Dijkstra implementation into LearnBug and see every edge relaxation live.