Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 01:12, 14 October 2024

Latest revision as of 02:09, 28 July 2025

(6 intermediate revisions by 5 users not shown)

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.

Line 37:

For this reason, <code>DijkstraAPSP</code> iterates over all nodes of the graph <math>G</math> and executes <code>DijkstraSSSP</code> with each as root node while storing the results in <math>D</math>.

The runtime of <code>DijkstraSSSP</code> is <math>O(|E|+|V|\log(|V|^2))</math> as we expect the graph to be represented using an [[adjacency matrix]].

Therefore <code>DijkstraAPSP</code> has a total sequential runtime of <math>O(|E||V|+|V|^32\log(|V|))</math>.

===Parallelization for up to |''V''| processors===

Line 107:

== Floyd–Warshall algorithm ==

The [[Floyd–Warshall algorithm]] solves the All-Pair-Shortest-Paths problem for directed graphs. With the [[adjacency matrix]] of a graph as input, it calculates shorter paths iterative. After |''V'' | iterations the distance-matrix contains all the shortest paths. The following describes a sequential version of the algorithm in pseudo code:

1 '''func''' Floyd_All_Pairs_SP(''A'') {

Line 119:

[[File:2d block-mapping.png|thumb|300x300px|partition of a matrix with 2-D block mapping]]

Where ''A'' is the [[adjacency matrix]], ''n'' = |''V'' | the number of nodes and ''D'' the distance matrix.

===Parallelization===

Line 175:

==Bibliography==

* Grama, A.: ''Introduction to [[parallel computing]].'' Pearson Education, 2003.

* {{citation

* Kumar, V.: ''[http://www.academia.edu/download/46545236/Scalability_of_parallel_algorithms_for_t20160616-15656-rc5uyt.pdf Scalability of Parallel Algorithms for the All-Pairs Shortest-Path Problem]{{dead link|date=July 2022|bot=medic}}{{cbignore|bot=medic}}.'' Journal of Parallel and Distributed Programming 13, 1991.

| last1 = Kumar | first1 = Vipin

| last2 = Singh | first2 = Vineet

| date = October 1991

| doi = 10.1016/0743-7315(91)90083-l

| issue = 2

| journal = Journal of Parallel and Distributed Computing

| pages = 124–138

| title = Scalability of parallel algorithms for the all-pairs shortest-path problem

| url = https://www-users.cse.umn.edu/~kumar001/papers/shortest-path.ps

| volume = 13}}

* Foster, I.: ''Designing and Building Parallel Programs'' (Online).

* Bindell, Fall: ''[httphttps://www.cs.cornell.edu/~bindel/class/cs5220-f11/code/path.pdf Parallel All-Pairs Shortest Paths]'' Applications of Parallel Computers, 2011.

[[Category:Graph algorithms]]