Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 16:57, 4 May 2024

Latest revision as of 02:09, 28 July 2025

(9 intermediate revisions by 7 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 10:

Let <math>G=(V,E,w)</math> be a directed Graph with the set of nodes <math>V</math> and the set of edges <math>E\subseteq V\times V</math>. Each edge <math>e \in E</math> has a weight <math>w(e)</math> assigned. The goal of the all-pair-shortest-paths problem is to find the shortest path between '''all''' pairs of nodes of the graph. For this path to be unique it is required that the graph does not contain cycles with a negative weight.

In the remainder of the article it is assumed that the graph is represented using an [[adjacency matrix]]. We expect the output of the algorithm to be a distancematrix <math>D</math>. In <math>D</math>, every entry <math>d-d_{i,j}</math> is the weight of the shortest path in <math>G</math> from node <math>i</math> to node <math>j</math>.

The [[Floyd algorithm]] presented later can handle negative edge weights, whereas the [[Dijkstra algorithm]] requires all edges to have a positive weight.

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]]