Authors: Weixi Chen (University of Southern California (USC)) and Runbang Hu and Yuede Ji (University of Texas, Arlington)
Abstract: Efficiently computing K-shortest path (KSP) on graphs is critical for many real-world applications. Existing solutions suffer from query-dependent pruning, limited parallelism, and redundant computation across repeated queries. To address such challenges, this paper presents KSPine, a fast parallel KSP framework. KSPine is built on block-cut+ tree (BC+ tree), a structural decomposition that identifies a compact, query-independent skeleton of the graph using biconnected components and articulation points. This skeleton allows KSPine to prune each query to a small structural subgraph and solve independent sub-KSP problems within each BiCC block in parallel. To combine local sub-KSP results into global top-K paths, we design a merging-based method with early stopping that reduces unnecessary computation. KSPine also introduces a hierarchical dynamic caching mechanism that reuses sub-KSP results across queries, avoiding redundant computation under continuous workloads. On six real-world graphs across various domains, KSPine achieves an average speedup of 1.5× over state-of-the-art methods.
Presentation: file