Parallel single-source shortest path algorithm

<p>A central problem in algorithmic <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> is the <a href="/facts/Shortest_path_problem/g4nsrswr">shortest path problem</a>. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex 
  
    
      
        s
      
    
    {\displaystyle s}
  
 to all other vertices in the graph. There are classical <a href="/facts/Sequential_algorithm/Jl5SxP1U">sequential algorithms</a> which solve this problem, such as <a href="/facts/Dijkstra%27s_algorithm/ehun88jl">Dijkstra's algorithm</a>. In this article, however, we present two <a href="/facts/Parallel_algorithm/nUPzEF4C">parallel algorithms</a> solving this problem.
</p><p>Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: <a href="/facts/Parallel_all-pairs_shortest_path_algorithm/F2G7MlYd">Parallel all-pairs shortest path algorithm</a>.
</p>

Parallel single-source shortest path algorithm open-in-new

Parallel single-source shortest path algorithm