Hopsets

Model

The hopset construction returns weighted pairs (u, v) → w. shortest_path_hopbound searches the original weighted graph together with those pairs, subject to max_hops.

Approximation contract

The explicit contract is checked by comparing bounded-hop distances against exact Dijkstra distances. The implementation uses epsilon as the multiplicative tolerance. The current tests cover this behavior on finite graph families; they do not make an unconditional performance promise.

Reproducibility

Pass both random_seed and, when byte-stable cross-machine output matters, an explicit omega. The default omega is aware of the detected BLAS vendor.