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

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: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.