Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 01:12, 14 October 2024

Revision as of 13:40, 3 January 2025

Line 1:

{{Multiple issues|

{{no footnotes|date=March 2018}}

{{manualhow-to|date=May 2019}}

}}

A central problem in algorithmic [[graph theory]] is the [[shortest path problem]]. Hereby, the problem of finding the shortest path between every pair of nodes is known as '''all-pair-shortest-paths (APSP)''' problem. As [[sequential algorithm]]s 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.