Engineering Invariants for Sub-Millisecond Routing
When a routing engine serves thousands of queries per second over a graph of $V = 10^6$ vertices, each individual query might touch only $k = 500$ vertices. Calling std::fill(dist.begin(), dist.end(), INF) at the start of every query touches $8\text{ MB}$ of RAM ($O(V)$ work), destroying the sub-linear advantage of A* and Bidirectional Search!
- $O(1)$ Generation-Counter Reset: Maintain a global
queryIdcounter and an arrayseenGen[0..V-1]. Whenever vertex $u$ is accessed during queryqueryId, ifseenGen[u] != queryId, lazily initializedist[u] = INF; parent[u] = -1; seenGen[u] = queryId;on-the-fly in $O(1)$ time! Total memory touched per query is strictly $O(k)$ where $k$ is the number of visited vertices. - Exact Bidirectional Dijkstra Stopping Criterion: Let $\mu$ be the minimum total path weight $d_F[w] + d_B[w]$ observed across any vertex $w$ reached by both directions so far (updated whenever an edge $(u, v)$ is relaxed and $v$ was already reached by the opposite search). The search can safely terminate if and only if: $$\min_{x \in Q_F} d_F[x] + \min_{y \in Q_B} d_B[y] \ge \mu$$ At that moment, no unexpanded path can possibly have total weight $< \mu$.
Consistent Symmetric Potentials for Bidirectional A*
In Bidirectional A*, the forward search targets $t$ using heuristic $h_F(u) \approx \delta(u, t)$, while the backward search targets $s$ using $h_B(u) \approx \delta(s, u)$. If we use $h_F$ and $h_B$ independently, their reduced edge weights $w_F(u, v) = w(u, v) - h_F(u) + h_F(v)$ and $w_B(u, v) = w(u, v) - h_B(v) + h_B(u)$ do not match! Goldberg and Harrelson (2005) proved that defining the average potential:
$$p_F(u) = \frac{h_F(u) - h_B(u)}{2}, \quad p_B(u) = -p_F(u) = \frac{h_B(u) - h_F(u)}{2}$$makes both directions run on the exact same consistent reduced weight function while preserving admissibility!
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
On a graph of $V = 10^6$ vertices, std::vector allocates and zeroes $8\text{ MB}$ of heap memory, taking ~1.8 milliseconds per call just in memset page faults. Reusing a persistent workspace struct with uint32_t epoch and vector reduces per-query initialization time from $1.8\text{ ms}$ to $0.4\text{ nanoseconds}$ (a single ++epoch instruction)!
Complexity Matrix
| Design Choice | Initialization Time / Query | Search Space ($D$ hops) | Correctness Guarantee |
|---|---|---|---|
| Naive Re-allocated Dijkstra | O(V) (memset bottleneck) |
O(b^D) | Exact |
| Epoch-Stamped A* (Consistent $h$) | O(1) (++epoch) |
Focused beam | Exact |
| Epoch-Stamped Bidirectional Dijkstra | O(1) (++epoch) |
O(2 · b^(D/2)) | Exact (with $\text{top}_F + \text{top}_B \ge \mu$) |
Complete Implementation: Epoch-Stamped Bidirectional Router with Path Splicing
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
struct RouterEdge { int to; long long weight; };
class BidirectionalRouter {
public:
explicit BidirectionalRouter(int n)
: numVertices(n), adj(n), revAdj(n),
dF(n), dB(n), pF(n), pB(n), stampF(n, 0), stampB(n, 0) {}
void addDirectedEdge(int u, int v, long long w) {
adj[u].push_back({v, w});
revAdj[v].push_back({u, w});
}
std::pair<long long, std::vector<int>> findShortestPath(int s, int t) {
if (s == t) return {0, {s}};
constexpr long long INF = std::numeric_limits<long long>::max() / 4;
++epoch;
using State = std::pair<long long, int>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pqF, pqB;
setF(s, 0, -1); pqF.emplace(0, s);
setB(t, 0, -1); pqB.emplace(0, t);
long long mu = INF;
int meetNode = -1;
while (!pqF.empty() && !pqB.empty()) {
if (pqF.top().first + pqB.top().first >= mu) break;
if (pqF.top().first <= pqB.top().first) {
auto [d, u] = pqF.top(); pqF.pop();
if (d > getF(u)) continue;
for (const auto& e : adj[u]) {
if (d + e.weight < getF(e.to)) {
setF(e.to, d + e.weight, u);
pqF.emplace(d + e.weight, e.to);
if (stampB[e.to] == epoch && d + e.weight + dB[e.to] < mu) {
mu = d + e.weight + dB[e.to];
meetNode = e.to;
}
}
}
} else {
auto [d, u] = pqB.top(); pqB.pop();
if (d > getB(u)) continue;
for (const auto& e : revAdj[u]) {
if (d + e.weight < getB(e.to)) {
setB(e.to, d + e.weight, u);
pqB.emplace(d + e.weight, e.to);
if (stampF[e.to] == epoch && dF[e.to] + d + e.weight < mu) {
mu = dF[e.to] + d + e.weight;
meetNode = e.to;
}
}
}
}
}
if (meetNode == -1) return {-1, {}};
std::vector<int> path;
for (int cur = meetNode; cur != -1; cur = pF[cur]) path.push_back(cur);
std::reverse(path.begin(), path.end());
for (int cur = pB[meetNode]; cur != -1; cur = pB[cur]) path.push_back(cur);
return {mu, path};
}
private:
int numVertices;
uint32_t epoch = 0;
std::vector<std::vector<RouterEdge>> adj, revAdj;
std::vector<long long> dF, dB;
std::vector<int> pF, pB;
std::vector<uint32_t> stampF, stampB;
long long getF(int u) const noexcept {
return stampF[u] == epoch ? dF[u] : std::numeric_limits<long long>::max() / 4;
}
long long getB(int u) const noexcept {
return stampB[u] == epoch ? dB[u] : std::numeric_limits<long long>::max() / 4;
}
void setF(int u, long long d, int p) noexcept { stampF[u] = epoch; dF[u] = d; pF[u] = p; }
void setB(int u, long long d, int p) noexcept { stampB[u] = epoch; dB[u] = d; pB[u] = p; }
};On a directed graph (e.g., road networks with one-way streets), the backward search from $t$ must traverse edges backward (in the transpose graph revAdj where edge $(u, v)$ is traversed from $v$ to $u$). Traversing forward outgoing edges from $t$ finds paths $t \leadsto m$ instead of $m \leadsto t$, routing cars the wrong way down one-way streets!