The Non-Negative Edge Greedy Settlement Proof
Why does the vertex $u \in V \setminus S$ with the minimum tentative distance $d[u]$ have $d[u] == \delta(s, u)$ (the true global shortest path distance) at the exact moment it is popped from the priority queue?
Theorem (CLRS Theorem 22.6): If $w(e) \ge 0$ for all $e \in E$, then whenever Dijkstra's algorithm extracts $u = \arg\min_{x \in V \setminus S} d[x]$ and adds $u$ to $S$, we have $d[u] = \delta(s, u)$.
Proof by Contradiction: Suppose $u$ is the first vertex added to $S$ for which $d[u] > \delta(s, u)$. Consider an actual shortest path $P: s \leadsto u$. Since $s \in S$ and $u \notin S$, let $(x, y)$ be the first edge along $P$ that crosses the cut $(S, V \setminus S)$, so $x \in S$ and $y \in V \setminus S$.
By the inductive hypothesis, when $x$ was settled, $d[x] = \delta(s, x)$, and relaxing $(x, y)$ set $d[y] \le d[x] + w(x, y) = \delta(s, y)$. Because the subpath $y \leadsto u$ along $P$ consists entirely of edges with non-negative weights ($w \ge 0$), we have:
Wait: $y \in V \setminus S$ and $d[y] < d[u]$, contradicting that $u$ was chosen as the minimum $d[\cdot]$ in $V \setminus S$! Notice where the proof breaks if a negative edge exists: $\delta(s, y) \le \delta(s, u)$ fails if the remaining suffix $y \leadsto u$ has negative total weight.
1. Lazy Duplicate Insertion vs. decrease-key
Standard C++ std::priority_queue and Python heapq do not expose a decrease_key handle. Instead, whenever an edge relaxation improves $d[v]$, we push a new pair (d[v], v) into the heap. When a pair (d_popped, u) is later extracted, we check if (d_popped > d[u]) continue; in $O(1)$ time—skipping stale entries in a single branch without maintaining an external index-to-heap-position map!
2. Dial's Algorithm (1969): $O(V \cdot C + E)$ Bucket Queue
When all edge weights are small integers $w(e) \in \{0, 1, \dots, C\}$ (generalizing 0-1 BFS where $C = 1$), any tentative distance pushed when popping $d[u]$ lies in $[d[u], d[u] + C]$. Maintaining a circular array of $C + 1$ buckets (indexed by $\text{dist} \bmod (C + 1)$) eliminates the $\log V$ heap factor completely, running in $O(V + E + \text{maxDist}) \le O(V \cdot C + E)$ linear time.
Compare Dijkstra’s uniform radial frontier against A* directional pruning f(u) = g(u) + h(u) and OSRM Contraction Hierarchies (shortcut insertion w(u,w)=w(u,v)+w(v,w) + upward rank-monotonic bidirectional search).
Invariant & State
Although Fibonacci heaps achieve $O(1)$ amortized decrease-key and $O(E + V \log V)$ total time, every node in a Fibonacci heap stores 4 pointers (parent, child, left, right), triggering pointer-chasing cache misses and high constant factors on extract-min. A contiguous array-backed 4-ary (d-ary) heap places all 4 children of a node inside a single 64-byte cache line (for 16-byte (dist, vertex) pairs), halving heap height to $\log_4 E$ and outperforming Fibonacci heaps by $3\times$ to $8\times$ on real road networks.
Complexity Matrix
| Priority Queue Structure | extract-min |
Relaxation / decrease-key |
Total Time Complexity |
|---|---|---|---|
| Flat Array Scan | O(V) | O(1) | O(V² + E) = O(V²) |
| Binary / 4-ary Heap (Lazy Push) | O(log E) | O(log E) | O((V + E) log V) |
| Fibonacci Heap | O(log V) amortized | O(1) amortized | O(E + V log V) |
| Dial's Circular Buckets ($w \le C$) | O(1) + bucket scan | O(1) list splice | O(V · C + E) |
Production Implementation: Lazy-Deletion Dijkstra & Dial's Bucket Queue
#include <vector>
#include <queue>
#include <limits>
struct WeightedArc {
int to;
long long weight;
};
std::vector<long long> dijkstra(int n, int source, const std::vector<std::vector<WeightedArc>>& adj) {
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> dist(n, INF);
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[source] = 0;
pq.emplace(0, source);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // Critical lazy deletion guard!
for (const auto& e : adj[u]) {
if (dist[u] + e.weight < dist[e.to]) {
dist[e.to] = dist[u] + e.weight;
pq.emplace(dist[e.to], e.to);
}
}
}
return dist;
}if (d > dist[u]) continue; Guard or Allowing Negative Edges to Re-PushWithout the if (d > dist[u]) continue; check at the top of the loop, a vertex pushed $k$ times will re-scan all of its outgoing edges $k$ times, degrading Dijkstra's runtime from $O(E \log V)$ to $O(V \cdot E)$ on dense graphs! Equally critical: if you allow a modified Dijkstra to re-push already-settled vertices on negative-weight edges (even without negative cycles), a chain of 3-vertex diamonds with exponentially decreasing negative weights forces $\Omega(2^{V/3})$ exponential vertex pops.