Parallel all-pairs shortest path algorithm: Difference between revisions

Revision as of 07:33, 21 April 2018

Revision as of 20:22, 9 May 2018

Line 12:

== Dijkstra algorithm ==

The [[Dijkstra algorithm]] originally was proposed as a solver for the single-source-shortest-paths problem. However, the algorithm can easily be used for solving the All-Pair-Shortest-Paths problem by executing the Single-Source varaintvariant with each node intin the role of the root node.

In pseudocode such an implementation could look as follows:

Line 77:

After substituting the definition of <math>k</math> this yields the total runtime for <code>DijkstraAPSP</code>: <math>O(\frac{|V|^3}{p} + \log p)</math>.

The main benefit of this parallelization is that it is not required anymore that every processor stores the entrieentire adjacency matrix.

Instead, it is sufficient when each processor within a partition only stores the columns of the adjacency matrix of the nodes for which he is responsible.

Given a partition size of <math>k</math>, each processor only has to store <math>\frac{|V|}{k}</math> columns of the adjacency matrix.

A downside, however, is that this parallelization comes with a communication ovheadoverhead due to the reduce- and broadcast-operations.

====Example====