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 G = ( V , E , w ) {\displaystyle G=(V,E,w)} be a directed Graph with the set of nodes V {\displaystyle V} and the set of edges E ⊆ V × V {\displaystyle E\subseteq V\times V} . Each edge e ∈ E {\displaystyle e\in E} has a weight w ( e ) {\displaystyle w(e)} 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 D {\displaystyle D} . In D {\displaystyle D} , every entry d i , j {\displaystyle d_{i,j}} is the weight of the shortest path in G {\displaystyle G} from node i {\displaystyle i} to node j {\displaystyle j} . 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:
1 func DijkstraSSSP(G,v) { 2 ... //standard SSSP-implementation here 3 return dv; 4 } 5 6 func DijkstraAPSP(G) { 7 D := |V|x|V|-Matrix 8 for i from 1 to |V| { 9 //D[v] denotes the v-th row of D 10 D[v] := DijkstraSSP(G,i) 11 } 12 }
In this example we assume that DijkstraSSSP takes the graph G {\displaystyle G} and the root node v {\displaystyle v} as input. The result of the execution in turn is the distancelist d v {\displaystyle d_{v}} . In d v {\displaystyle d_{v}} , the i {\displaystyle i} -th element stores the distance from the root node v {\displaystyle v} to the node i {\displaystyle i} . Therefore the list d v {\displaystyle d_{v}} corresponds exactly to the v {\displaystyle v} -th row of the APSP distancematrix D {\displaystyle D} . For this reason, DijkstraAPSP iterates over all nodes of the graph G {\displaystyle G} and executes DijkstraSSSP with each as root node while storing the results in D {\displaystyle D} . The runtime of DijkstraSSSP is O ( | E | + | V | log ( | V | ) ) {\displaystyle O(|E|+|V|\log(|V|))} as we expect the graph to be represented using an adjacency matrix. Therefore DijkstraAPSP has a total sequential runtime of O ( | E | | V | + | V | 2 log ( | V | ) ) {\displaystyle O(|E||V|+|V|^{2}\log(|V|))} .
… excerpt ends here. Continue reading the full article.
