An Empirical Comparison of k-Shortest Simple Path Algorithms on Multicores
Refereed Conference Meeting Proceeding
We consider the loop less k-shortest path (KSP) problem. Although this problem has been studied in the sequential setting for at least the last two decades, no good parallel implementations are known. In this paper, we provide (i) a first systematic empirical comparison of various KSP algorithms and heuristic optimisations, (ii) care- fully engineer various parallel implementations of these sequential algorithms and (iii) perform an extensive study of these parallel implementations on a range of graph classes and multicore architec- tures to determine the best algorithm and parallelization strategy for different graph classes. We find that even though the worst-case complexity of the best undirected KSP algorithm O(k(m + n logn)) is significantly better than that of the popular and considerably simpler directed KSP algorithm O(kn(m + n logn)), the two algorithms are fairly com- petitive in terms of their empirical performance on small diameter graphs. Furthermore, we show that a few simple optimisations help to bridge the gap between these KSP algorithms even more. How- ever, on moderate to large diameter graphs, the undirected KSP algorithm is considerably faster than the directed algorithms, both in sequential and parallel settings. In terms of the parallelisation strategy, simply replacing the shortest path subroutine by parallel ∆-stepping algorithm can provide a good speed-up for many KSP algorithms on random graphs. In contrast, for graphs with skewed degree distribution, a more complex strategy of parallelizing the different deviations and then parallelizing the shortest path compu- tation inside the deviations with the remaining threads, provides a better performance.
47th International Conference on Parallel Processing Article No. 78
Digital Object Identifer (DOI):
National University of Ireland, Dublin (UCD)
Open access repository: