Finding Shortest Paths Faster With Less Data

WormHole is a two-phase algorithm for answering many shortest-path queries on large, power-law (core-periphery) networks with limited node access. It first preprocesses just enough of the graph to extract a dense, sublinear “inner ring” core. At query time, it runs truncated BiBFS to detect same-community cases; otherwise it routes both ends to the outer ring, hops into the inner ring, and finds a path there—returning exact paths in common cases and near-shortest paths otherwise. The payoff: far fewer node queries and memory, fast responses, and low mean additive error across queries.