The WormHole Algorithm for Approximate Shortest Paths in Large Graphs

WormHole is an efficient graph algorithm designed to compute approximate shortest paths by combining structural decomposition with a bidirectional BFS routing phase. It preprocesses a graph into an “inner ring” to enable fast, accurate queries, balancing speed and space efficiency. Two variants, WormHole𝐸 and WormHole𝑀, adapt the approach for different needs—one prioritizing memory economy, the other optimized for rapid inquiries through partial graph indexing.