Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Parallel all-pairs shortest path algorithm
open-in-new
<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>. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As <a href="/facts/Sequential_algorithm/Jl5SxP1U">sequential algorithms</a> for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced. </p><p>Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: <a href="/facts/Parallel_single-source_shortest_path_algorithm/vWsn65at">Parallel single-source shortest path algorithm</a>. </p>