Finding Simple Shortest-Paths via Centroids

Abstract

Finding an arbitrary number of shortest paths in a graph is a fundamental problem in Graph Theory and Artificial Intelligence with numerous applications to real-world problems. While some algorithms produce paths which might contain loops, the most interesting and challenging problem variant consists of finding simple (or loopless) paths. This problem has been addressed with algorithms which always conduct an arbitrary number of Dijkstra searches. While the current state-of-the-art leverages the notion of sidetrack edge, a new development upon sidetrack edges has been recently introduced which can be used to produce non-simple paths very efficiently, centroids. In this paper, centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijkstra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency. Experimental results across various domains show substantial improvements over the current state of the art, both in runtime and memory usage.