Improving Space Efficiency With Path Length Prediction for Finding $k$ Shortest Simple Paths

Finding mbi k shortest simple paths in a directed graph is a fundamental problem in many engineering applications. Most existing algorithms such as Yen´s algorithm and its variants have polynomial worst-case time complexity, but their average-case running time is very high. The heuristic algorithm MPS can run significantly faster in practice. However, it requires an excessive amount of memory space. In this paper, we provide a new heuristic algorithm that achieves high space efficiency while maintaining similar average-case running time. We first propose a sidetrack representation of path, with which a path can be stored in mbi O(1) space. We then show how to categorize a candidate path as either partial or complete, and restrict the number of paths added to the queue. In addition, we provide an empirical equation that can very accurately predict the mbi kth shortest path length, provided that a much smaller number of shortest paths have been found. Extensive experiments prove that our algorithm can achieve an mbi O(n) speedup in practice over Yen´s algorithm. In comparison with MPS, it runs up to three times faster and uses less space by an order of magnitude.