# A New k-Shortest Path Search Approach based on Graph Reduction

Preprint · Yasuo Yamane, Hironobu Kitajima

- Archive id: arxiv:1908.06460
- Published: 2019-08-18
- arXiv: https://arxiv.org/abs/1908.06460
- Citations: 0
- Source URL: https://arxiv.org/abs/1908.06460
- PDF: https://arxiv.org/pdf/1908.06460
- Provenance: arxiv

## Abstract

We present a new approach called GR (Graph Reduction) algorithm for searching loop-less k-shortest paths (1st to k-th shortest paths) in a graph based on graph reduction. Let a source vertex and a target vertex of k-shortest paths be v\_s and v\_t respectively. First our approach computes shortest paths to every vertex from v\_s and v\_t respectively, and reduce a graph to a subgraph that contains all vertices and edges of loop-less k-shortest paths using the already computed shortest paths, and apply an existing k-shortest path search algorithm to the reduced graph. A graph can be reduced quickly after computing the shortest paths using them, therefore a very efficient search can be achieved. In an experiment using a hypercube graph which has 16384 vertices where k=128, the number of vertices is reduced to about 1/22, and a variant of Dijkstra algorithm for k-shortest path search were speeded up by about 365 times. We implemented a fast k-shortest path variant of bidirectional Dijkstra algorithm (k-biDij) which is the state-of-the-art algorithm and the fastest as long as we know, GR outperforms k-biDij in dense scale-free graphs. However, k-biDij outperforms GR in hypercube-shaped and sparse scale-free graphs, but even then GR can also speed up it by 12.3 and 2.0 times respectively by precomputing all-pairs shortest paths. We also show the graph reduction can be done in time complexity O(m + n log n). We also introduce our improvements to k-biDij simply.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.