Fewest Hops Is Not Fastest

Take a typical case, made up for illustration. A delivery planner used BFS to route vans and picked a route with only a few road segments, straight through an old town's narrow streets. A route with more segments along the ring road was 40 minutes faster. Later, someone modelled toll refunds as negative-weight edges, and the planner started returning routes that were wrong without raising any error.

Dijkstra's algorithm finds the cheapest path when every edge has a non-negative cost. It is short to write, and it is the base of many routing and network tools. Below is the version that actually ships: a binary heap with “push duplicates, skip stale entries”, stopping at the target, A* when you have a good estimate, and what to use when weights go negative.

If your shortest paths look wrong
  • You learned Dijkstra in school and never wrote it for real
  • You can't explain why .NET's PriorityQueue doesn't support decrease-key
  • You don't know when to reach for A* over Dijkstra
  • You used Dijkstra on a graph with negative weights and got a wrong answer