Abstract: 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 ParSP2 that leverage these constraints solve the problem faster and more efficiently in key metrics. In single threaded execution, we show how SP1 and SP2 out-perform Dijsktra by more than 60\% in many cases. In multi-threaded execution we show how our algorithms compare favorably to delta-stepping in the ability to establish the shortest path between the source and the median node much faster and scaling better as the graph size increases.