Finding Top K Shortest Simple Paths with Improved Space Efficiency

Finding top-K shortest paths is fundamental and crucial to many graph applications, but known to be nontrivial over large graph data and large value of K. This problem becomes much more challenging when the shortest paths require to be simple (paths without loops). When searching for top-K shortest simple paths, MPS algorithm is a practically fast and efficient scheme based on the famous Yen's algorithm. In this paper, we propose an improved MPS algorithm which can significantly reduce the memory consumption and increase the execution speed compared to the original MPS algorithm. First, we design a pruning scheme during the construction of pseudo-tree, such that only the shortest path in each iteration would be added to the pseudo-tree, instead of adding all possible candidate paths as that in the original MPS algorithm. Second, we modify the pseudo-tree of shortest-path candidates with reversed order and internal ID, such that the shortest paths can be retrieved directly from the constructed pseudo-tree without explicitly storing all candidate paths. Furthermore, we evaluate the performance in terms of running time and memory consumption in both synthetic and real graphs with millions of vertices and edges. Compared to the original MPS algorithm, experimental results show that our improved MPS algorithm can bring up to 6x performance gain in both running time and memory consumption.