Efficient Parallel Shortest Path Algorithms
David R. Alves, Madan S. Krishnakumar, Vijay K. Garg · 2020
Finding the shortest path between nodes in a graph has wide applications in many important areas such as transportation and computer networks. However, the current reference algorithms for this task, Dijkstra's for single threaded environments and Δ-stepping for multi-threaded ones, leave performance and efficiency on the table by not taking advantage of additional information available about the graph. In this paper we present and experimentally evaluate novel algorithms SP1, SP2and ParSP2that leverage these constraints to solve the problem faster and more efficiently in key metrics. In single threaded execution, we show how SP1and SP2out-perform Dijsktra's algorithm by up to 46%. In multi-threaded execution we show how our algorithms compare favorably to Δ-stepping algorithm in the ability to establish the shortest path between the source and the median node.