Parallel all-pairs shortest path algorithm
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 algorithms 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. Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: Parallel single-source shortest path algorithm. Problem definition. Let formula_1 be a  directed Graph with the set of nodes formula_2 and the set of edges formula_3. Each edge formula_4 has a weight formula_5 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 formula_6. In formula_6, every entry formula_8  is the weight of the shortest path in formula_9 from node formula_10 to node formula_11. The Floyd algorithm presented later can handle negative edge weights, whereas the Dijkstra algorithm requires all edges to have a positive weight. 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 variant with each node in the role of the root node. In pseudocode such an implementation could look as follows: In this example we assume  that codice_1 takes the graph formula_9 and the root node formula_13 as input. The result of the execution in turn is the distancelist formula_14. In formula_14, the formula_10-th element stores the distance from the root node formula_13 to the node formula_10. Therefore the list formula_14 corresponds exactly to the formula_13-th row of the APSP distancematrix formula_6. For this reason, codice_2 iterates over all nodes of the graph formula_9 and executes codice_1 with each as root node while storing the results in formula_6. The runtime of codice_4 is formula_24 as we expect the graph to be represented using an  adjacency matrix. Therefore codice_2 has a total sequential runtime of formula_25. Parallelization for up to |"V"| processors. A trivial parallelization can be obtained by parallelizing the loop of codice_2 in line"8". However, when using the sequential codice_4 this limits the number of processors to be used by the number of iterations executed in the loop. Therefore, for this trivial parallelization formula_26 is an upper bound for the number of processors. For example, let the number of processors formula_27 be equal to the number of nodes formula_26. This results in each processor executing codice_4 exactly once in parallel. However, when there  are only for example formula_29 processors available, each processor has to execute codice_4 twice. In total this yields a runtime of formula_30, when formula_26 is a multiple of formula_27. Consequently, the efficiency of this parallelization is perfect: Employing formula_27 processors reduces the runtime by the factor formula_27. Another benefit of this parallelization is that no communication between the processors is required. However, it is required that every processor has enough local memory to store the entire adjacency matrix of the graph. Parallelization for more than |"V"| processors. If more than formula_26 processors shall be used for the parallelization, it is  required that multiple processors take part of the codice_4 computation. For this reason, the parallelization is split across into two levels. For the first level the processors are split into formula_26 partitions. Each partition is responsible for the computation of a single row of the distancematrix formula_6. This means each partition has to evaluate one codice_4 execution with a fixed root node. With this definition each partition has a size of formula_38 processors. The partitions can perform their computations in parallel as the results of each are independent of each other. Therefore, the parallelization presented in the previous section corresponds  to a partition size of 1 with formula_39 processors. The main difficulty is the parallelization of multiple processors executing codice_4 for a single root node. The idea for this parallelization is to distribute the management of the distancelist formula_14 in DijkstraSSSP within the partition. Each processor in the partition therefore is exclusively responsible for formula_41 elements of formula_14. For example, consider formula_43 and formula_44: this yields a partition size of formula_45. In this case, the first processor of each partition is responsible for formula_46, formula_47 and the second processor is responsible for formula_48 and formula_49. Hereby, the total distance lists  is formula_50. The codice_4 algorithm mainly consists of the repetition of two steps: First, the nearest node formula_51 in the distancelist formula_14 has to be found. For this node the shortest path already has been found. Afterwards the distance of all neighbors of formula_51 has to be adjusted in formula_14. These steps have to be altered as follows because for the parallelization formula_14 has been distributed across the partition: The total runtime of such an iteration of codice_4 performed by a partition of size formula_69 can be derived based on the performed subtasks: For formula_26-iterations this results in a  total runtime of formula_74. After substituting the definition of formula_69 this yields the total runtime for codice_2: formula_76 columns of the adjacency matrix. A downside, however, is that this parallelization comes with a communication overhead due to the reduce- and broadcast-operations. Example. The graph used in this example is the one presented in the image with four nodes. The goal is to compute the distancematrix with formula_44 processors. For this reason, the processors are divided into four partitions with two processors each. For the illustration we focus on the partition which is responsible for the computation of the shortest  paths from node A to all other nodes. Let the processors of this partition be named p1 and p2. The computation of the distancelist across the different iterations is visualized in the second image. The top row in the image corresponds to formula_78 after the initialization, the bottom one to formula_78 after the termination of the algorithm. The nodes are distributed in a way that p1 is responsible for the nodes A and B, while p2 is responsible for C and D. The distancelist formula_78 is distributed according to this. For the second iteration the subtasks executed are shown explicitly  in the image: Floyd algorithm. The Floyd 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: Where "A" is the adjacency matrix, "n" = |"V"| the number of nodes and "D" the distance matrix. For a more detailed description of the sequential algorithm look up Floyd–Warshall algorithm. Parallelization. The basic idea to parallelize the algorithm is to partition the matrix  and split the computation between the processes. Each process is assigned to a specific part of the matrix. A common way to achieve this is 2-D Block Mapping. Here the matrix is partitioned into squares of the same size and each square gets assigned to a process. For an formula_86-matrix and "p" processes each process calculates a formula_87 sized part of the distance matrix. For formula_88 processes each would get assigned to exactly one element of the matrix. Because of that the parallelization only scales to a maximum of formula_89 processes. In the following we refer with formula_90  to the process that is assigned to the square in the i-th row and the j-th column. As the calculation of the parts of the distance matrix is dependent on results from other parts the processes have to communicate between each other and exchange data. In the following we refer with formula_91 to the element of the i-th row and j-th column of the distance matrix after the k-th iteration. To calculate formula_91 we need the elements formula_93, formula_94 and formula_95 as specified in line 6 of the algorithm. formula_93 is available to each process  as it was calculated by itself in the previous iteration. Additionally each process needs a part of the k-th row and the k-th column of the formula_97 matrix. The formula_94 element holds a process in the same row and the formula_95 element holds a process in the same column as the process that wants to compute formula_91. Each process that calculated a part of the k-th row in the formula_97 matrix has to send this part to all processes in its column. Each process that calculated a part of the k-th column in the formula_97 matrix  has to send this part to all processes in its row. All this processes have to do a one-to-all-broadcast operation along the row or the column. The data dependencies are illustrated in the image below. For the 2-D block mapping we have to modify the algorithm as follows: In line 5 of the algorithm we have a synchronisation step to ensure that all processes have the data necessary to compute the next iteration. To improve the runtime of the algorithm we can remove the synchronisation step without affecting the correctness of the algorithm. To achieve that  each process starts the computation as soon as it has the data necessary to compute its part of the matrix. This version of the algorithm is called pipelined 2-D block mapping. Runtime. The runtime of the sequential algorithm is determined by the triple nested for loop. The computation in line 6 can be done in constant time (formula_111). Therefore, the runtime of the sequential algorithm is formula_112. 2-D block mapping. The runtime of the parallelized algorithm consists of two parts. The time for the computation and the part for communication and data transfer between the processes. As there  is no additional computation in the algorithm and the computation is split equally among the "p" processes, we have a runtime of formula_113 for the computational part. In each iteration of the algorithm there is a one-to-all broadcast operation performed along the row and column of the processes. There are formula_114 elements broadcast. Afterwards there is a synchronisation step performed. How much time these operations take is highly dependent on the architecture of the parallel system used. Therefore, the time needed for communication and data transfer in the algorithm is formula_115. For the whole algorithm we have the  following runtime: Pipelined 2-D block mapping. For the runtime of the data transfer between the processes in the pipelined version of the algorithm we assume that a process can transfer "k" elements to a neighbouring process in formula_117 time. In every step there are formula_118 elements of a row or a column send to a neighbouring process. Such a step takes formula_119 time. After formula_120 steps the relevant data of the first row and column arrive at process formula_121 (in formula_122 time). The values of successive rows and columns follow after time formula_123 in a pipelined mode. Process formula_124  finishes its last computation after O(formula_125) + O(formula_126) time. Therefore, the additional time needed for communication in the pipelined version is formula_122. The overall runtime for the pipelined version of the algorithm is: