Dijkstra's shortest path

Cheapest-cost paths over non-negative weighted edges. BFS with a priority queue instead of a plain queue.

Weights break BFS

• BFS finds fewest EDGES; weights make that ≠ cheapest
• One long edge can cost more than three short ones
• Fix: expand the closest node by total WEIGHT, using a min-heap
• Settle-on-pop: first time a node comes off the heap, its distance is final

Watch distances settle

Numbers in nodes = tentative distance (∞ → falls as edges relax). Green = settled · blue = frontier · grey numbers = edge weights.

The direct edge is a trap

• 0→6 direct edge: weight 10
• Dijkstra takes 0→1→3→6: cost 3
• Cheapest ≠ fewest hops
• Random graphs: BFS path ~25% costlier; worst case unbounded

Relaxation + non-negativity

• Relax: if dist[u]+w < dist[v]: dist[v] = dist[u]+w (only ever lowers)
• Correct because non-negative weights ⇒ settled = final
• ONE negative edge breaks it → Bellman-Ford
• O((V+E) log V) with a binary heap

Takeaway

The heaps chapter pays off here: the priority queue is the whole trick. networkx.single_source_dijkstra in production; A* and Prim are this + one idea. Next: Bellman-Ford, for negative weights.