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.
- You learned Dijkstra in school and never wrote it for real
- You can't explain why .NET's
PriorityQueuedoesn'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