Dijkstra's algorithm and the non-negative-weight requirement
/ DYKE-struh /
Imagine ink spreading outward from the source through the road network, but the ink reaches a city only after travelling the cheapest route to it, so cities light up strictly in order of how far they are from the source — nearest first. Dijkstra's algorithm is exactly this expanding frontier. It repeatedly grabs the un-finalized vertex with the smallest tentative distance, declares that distance final, and uses it to relax its outgoing edges. Because it always finalizes the closest remaining vertex, each vertex's distance is settled exactly once.
Concretely, keep all vertices in a priority queue keyed by d. Start with d[source] = 0, everything else infinity. Repeat: extract the vertex u with smallest d (this d[u] is now its final shortest distance), and relax every edge (u, v), lowering d[v] in the queue if d[u] + w(u,v) is smaller. Why is the extracted d[u] guaranteed final? Because all edge weights are non-negative, any not-yet-finalized path to u must pass through some other un-finalized vertex x first, and d[x] >= d[u] (u was the minimum), so detouring through x only adds non-negative weight and cannot beat d[u]. With a binary heap this runs in O((V + E) log V); with a Fibonacci heap, O(E + V log V).
Dijkstra is the workhorse of GPS and network routing whenever costs cannot be negative, which is the usual case for distances and times. The non-negativity requirement is not a footnote — it is load-bearing. With a negative edge, the 'closest unfinished vertex is final' claim collapses: a vertex you already finalized could later be reached more cheaply through a negative edge you had not yet explored, and Dijkstra never revisits a finalized vertex, so it returns a wrong answer. If you have negative weights, use Bellman-Ford or first reweight with Johnson's algorithm; do not patch Dijkstra and hope.
A trap for Dijkstra: vertices s, a, b with edges s->a (1), s->b (4), a->b (-3). True dist(b) = 1 + (-3) = -2. But Dijkstra finalizes b at d[b] = 4 the moment it extracts it (after s, before processing a's negative edge could ever help), locking in 4 and missing -2. Non-negative weights are what make 'finalize the minimum' valid.
With one negative edge Dijkstra finalizes b too early; non-negativity is exactly the assumption that breaks here.
Dijkstra is simply WRONG on graphs with negative edge weights — not slow, wrong. It can finalize a vertex before a cheaper negative-edge route is discovered and never reconsiders it.