Bounded Multi-Source Shortest Paths: Algorithm Theory, Implementation Comparison, and Benchmarking
Given a directed graph $G=(V,E)$ with non-negative weights $w:E\to \mathbb{R}_{\ge 0}$, a set of sources $S\subseteq V$ with initial offsets $d_0(s)$ (usually 0), and a distance bound $B$, compute:
This is Dijkstra from multiple sources that halts when the next tentative key would be $\ge B$.
The algorithm maintains the same invariant as Dijkstra: a node is popped exactly once with its final shortest distance. The only change is the early-exit condition.
For all v ∈ V: dist[v] ← +∞
For each source s ∈ S:
if d₀(s) < B:
dist[s] ← d₀(s)
push (d₀(s), s) into min-priority-queue
B' ← B
while priority_queue is not empty:
(d, u) ← pop_min()
if d ≠ dist[u]:
continue // Skip stale entry
if d ≥ B:
B' ← d
break // Early termination
mark u as processed
for each edge (u, v, w):
nd ← d + w
if nd < dist[v] and nd < B:
dist[v] ← nd
push (nd, v) into priority_queue
elif nd ≥ B:
B' ← min(B', nd) // Track boundary
Return: $(U, B’)$ where $U$ are the processed vertices.
Multi-source insight: Seeding multiple entries is trivial. All standard Dijkstra proofs still apply.
Dijkstra Invariant: When a node $u$ is popped, $\text{dist}[u] = d(u)$ (true shortest distance).
Proof sketch: The proof carries over from standard Dijkstra because:
Boundary Lemma: Let $U$ be nodes popped before exit. Then: \(B' = \min\{\hat d(x)\mid x\in V\setminus U\}\)
This is the smallest tentative distance still in the heap (or discovered and $\ge B$).
Properties:
Let $U={v\mid d(v)<B}$ and $E(U)={(u,v)\in E\mid u\in U}$.
Breakdown:
| Each vertex in $U$ is popped exactly once: $\mathcal{O}( | U | \log | U | )$ |
| Each edge from $U$ is relaxed at most once: $\mathcal{O}( | E(U) | \log | U | )$ |
| Heap operations: $\mathcal{O}(\log | U | )$ per operation |
| Worst case: When $B$ is large, $ | U | =n$ and $ | E(U) | =m$, giving standard $\mathcal{O}((m+n)\log n)$. |
| Best case: When $B$ is small, $ | U | \ll n$, achieving significant speedup. |
Components:
| Priority queue: $\mathcal{O}( | U | )$ at peak |
Asymptotically dominated by graph storage.
| Time: No change to big-O complexity. Practically lowers the radius needed to reach a given explored fraction $f = | U | /n$. |
Intuition: You explore shallow balls from multiple centers instead of a deep ball from one center.
| Define $f = | U | /n$ as the fraction of vertices explored. |
Relative speedup compared to full Dijkstra: \(\text{Speedup} \approx \frac{1}{f \log(fn) + \epsilon}\)
where $\epsilon$ accounts for overhead.
Key insight: When $f \ll 1$, BMSSP provides substantial speedup exactly as predicted by the model.
✅ Small distance bounds relative to graph diameter
✅ Range queries and proximity search
✅ Iterative algorithms that gradually increase $B$
✅ Sparse exploration where $f = |U|/n \ll 1$
❌ Large bounds approaching graph diameter ($f \to 1$)
❌ Small integer weights (specialized queues like Dial are better)
❌ Highly parallel scenarios (Δ-stepping might dominate)
| Algorithm | Weight Type | Time Complexity | Space | Best Use Case |
|---|---|---|---|---|
| BMSSP (Binary Heap) | Non-negative | $\mathcal{O}((m+n)\log n)$ | $\Theta(n+m)$ | Bounded search, $f \ll 1$ |
| Dijkstra (Binary Heap) | Non-negative | $\mathcal{O}((m+n)\log n)$ | $\Theta(n+m)$ | General-purpose baseline |
| Dijkstra (Fibonacci) | Non-negative | $\mathcal{O}(m + n\log n)$ | High constants | Theoretical interest |
| Dial/Bucket Queue | Integer $[0,C]$ | $\mathcal{O}(m + nC)$ | $\Theta(n+m+C)$ | Small integer weights |
| Δ-stepping | Non-negative | Near-linear per level | Buckets + frontier | Parallel processing |
| A* | Non-negative + heuristic | Like Dijkstra on explored set | Like Dijkstra | Problem-specific heuristics |
| Bellman-Ford | Any (with negative) | $\mathcal{O}(nm)$ | $\Theta(n)$ | Negative edge weights |
| Heuristic available: A* can explore less than $ | U | $ for same bound |
For iterative algorithms that increase $B$:
// Reuse previous distances as warm start
// dist array preserves optimality due to monotonicity
let (new_explored, new_boundary) = bmssp_continue(graph, dist, prev_boundary, new_bound);
This preserves optimality because shortest path distances are monotone with respect to the bound.
If $B_1 \leq B_2$, then $U_1 \subseteq U_2$ and $B’_1 \geq B’_2$.
All distances in $U$ are exact shortest path distances from the nearest source.
Every vertex $v$ with $d(v) < B$ is included in $U$.
$B’$ is the minimum distance among all vertices not in $U$, providing the exact threshold for the next expansion phase.
| ← Back to Home | Implementations → |