Efficient Parallel Shortest Path Algorithms

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 Delta-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, SP2 and ParSP(2) that leverage these constraints to solve the problem faster and more efficiently in key metrics. In single threaded execution, we show how SP1 and SP2 out-perform Dijsktra's algorithm by up to 46%. In multi-threaded execution we show how our algorithms compare favorably to Delta-stepping algorithm in the ability to establish the shortest path between the source and the median node.