A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex formula_1 to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem.
Another variation of the problem is the all-pairs-shortest-paths (APSP) problem, which also has parallel approaches: Parallel all-pairs shortest path algorithm.
Problem definition.
Let formula_2 be a directed graph with formula_3 nodes and formula_4 edges. Let formula_1 be a distinguished vertex (called "source") and formula_6 be a function assigning a non-negative real-valued weight to each edge. The goal of the single-source-shortest-paths problem is to compute, for every vertex formula_7 reachable from formula_1, the weight of a minimum-weight path from formula_1 to formula_7, denoted by formula_11 and abbreviated formula_12. The weight of a path is the sum of the weights of its edges. We set formula_13 if formula_7 is unreachable from formula_15.
Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; formula_16 is always formula_17 or the weight of some path from formula_1 to formula_7 and hence an upper bound on formula_12. Tentative distances are improved by performing edge relaxations, i.e., for an edge formula_21 the algorithm sets formula_22.
For all parallel algorithms we will assume a PRAM model with concurrent reads and concurrent writes.
Delta stepping algorithm.
The delta stepping algorithm is a label-correcting algorithm, which means the tentative distance of a vertex can be corrected several times via edge relaxations until the last step of the algorithm, when all tentative distances are fixed.
The algorithm maintains eligible nodes with tentative distances in an array of buckets each of which represents a distance range of size formula_23. During each phase, the algorithm removes all nodes of the first nonempty bucket and relaxes all outgoing edges of weight at most formula_23. Edges of a higher weight are only relaxed after their respective starting nodes are surely settled. The parameter formula_23 is a positive real number that is also called the "step width" or "bucket width".
Parallelism is obtained by concurrently removing all nodes of the first nonempty bucket and relaxing their outgoing light edges in a single phase. If a node formula_7 has been removed from the current bucket formula_27 with non-final distance value then, in some subsequent phase, formula_7 will eventually be reinserted into formula_27 , and the outgoing light edges of formula_7 will be re-relaxed. The remaining heavy edges emanating from all nodes that have been removed from formula_27 so far are relaxed once and for all when formula_27 finally remains empty. Subsequently, the algorithm searches for the next nonempty bucket and proceeds as described above.
The maximum shortest path weight for the source node formula_1 is defined as formula_34, abbreviated formula_35. Also, the size of a path is defined to be the number of edges on the path.
We distinguish light edges from heavy edges, where light edges have weight at most formula_23 and heavy edges have weight bigger than formula_23 .
Following is the delta stepping algorithm in pseudocode:
 1 foreach formula_38 do formula_39
 2 formula_40; (*Insert source node with distance 0*)
 3 while formula_41 do (*A phase: Some queued nodes left (a)*)
 4 formula_42 (*Smallest nonempty bucket (b)*)
 5 formula_43 (*No nodes deleted for bucket B[i] yet*)
 6 while formula_44 do (*New phase (c)*)
 7 formula_45 (*Create requests for light edges (d)*)
 8 formula_46 (*Remember deleted nodes (e)*)
 9 formula_47 (*Current bucket empty*)
 10 formula_48 (*Do relaxations, nodes may (re)enter B[i] (f)*)
 11 formula_49 (*Create requests for heavy edges (g)*)
 12 formula_48 (*Relaxations will not refill B[i] (h)*)
 13
 14 function formula_51:set of Request
 15 return formula_52
 16
 17 procedure formula_48
 18 foreach formula_54 do formula_55
 19
 20 procedure formula_55 (*Insert or move w in B if formula_57*)
 21 if formula_58 then
 22 formula_59 (*If in, remove from old bucket*)
 23 formula_60 (*Insert into new bucket*)
 24 formula_61
Example.
Following is a step by step description of the algorithm execution for a small example graph. The source vertex is the vertex A and formula_23 is equal to 3.
At the beginning of the algorithm, all vertices except for the source vertex A have infinite tentative distances.
Bucket formula_63 has range formula_64, bucket formula_65 has range formula_66 and bucket formula_67 has range formula_68.
The bucket formula_63 contains the vertex A. All other buckets are empty.
The algorithm relaxes all light edges incident to formula_63, which are the edges connecting A to B, G and E.
The vertices B,G and E are inserted into bucket formula_65. Since formula_63 is still empty, the heavy edge connecting A to D is also relaxed.
Now the light edges incident to formula_65 are relaxed. The vertex C is inserted into bucket formula_67. Since now formula_65 is empty, the heavy edge connecting E to F can be relaxed.
On the next step, the bucket formula_67 is examined, but doesn't lead to any modifications to the tentative distances.
The algorithm terminates.
Runtime.
As mentioned earlier, formula_35 is the maximum shortest path weight.
Let us call a path with total weight at most formula_23 and without edge repetitions a formula_23-path.
Let formula_80 denote the set of all node pairs formula_81 connected by some formula_23-path formula_83 and let formula_84. Similarly, define formula_85 as the set of triples formula_86 such that formula_87 and formula_88 is a light edge and let formula_89.
The sequential delta-stepping algorithm needs at mostformula_90 operations. A simple parallelization runs in time formula_91 .
If we take formula_92 for graphs with maximum degree formula_93 and random edge weights uniformly distributed in formula_94, the sequential version of the algorithm needs formula_95 total average-case time and a simple parallelization takes on average formula_96.
Graph 500.
The third computational kernel of the Graph 500 benchmark runs a single-source shortest path computation. The reference implementation of the Graph 500 benchmark uses the delta stepping algorithm for this computation.
Radius stepping algorithm.
For the radius stepping algorithm, we must assume that our graph formula_97 is undirected.
The input to the algorithm is a weighted, undirected graph, a source vertex, and a target radius value for every vertex, given as a function formula_98. The algorithm visits vertices in increasing distance from the source formula_1. On each step formula_100, the Radius-Stepping increments the radius centered at formula_1 from formula_102 to formula_103 , and settles all vertices formula_7 in the annulus formula_105.
Following is the radius stepping algorithm in pseudocode:
 Input: A graph formula_106, vertex radii formula_107, and a source node formula_1.
 Output: The graph distances formula_109 from formula_1.
 1 formula_111, formula_112
 2 foreach formula_113 do formula_114, formula_115, formula_116
 3 while formula_117 do
 4 formula_118
 5 repeat 
 6 foreach formula_119 s.t formula_120 do
 7 foreach formula_121 do
 8 formula_122
 9 until no formula_123 was updated
 10 "formula_124"
 11 formula_125
 12 return formula_109
For all formula_127, define formula_128 to be the neighbor set of S. During the execution of standard breadth-first search or Dijkstra's algorithm, the frontier is the neighbor set of all visited vertices.
In the Radius-Stepping algorithm, a new round distance formula_103 is decided on each round with the goal of bounding the number of substeps. The algorithm takes a radius formula_130 for each vertex and selects a formula_103 on step formula_100 by taking the minimum formula_133 over all formula_7 in the frontier (Line 4).
Lines 5-9 then run the Bellman-Ford substeps until all vertices with radius less than formula_103 are settled. Vertices within formula_136 are then added to the visited set formula_137.
Example.
Following is a step by step description of the algorithm execution for a small example graph. The source vertex is the vertex A and the radius of every vertex is equal to 1.
At the beginning of the algorithm, all vertices except for the source vertex A have infinite tentative distances, denoted by formula_138 in the pseudocode.
All neighbors of A are relaxed and formula_139.
The variable formula_140 is chosen to be equal to 4 and the neighbors of the vertices B, E and G are relaxed. formula_141
The variable formula_142 is chosen to be equal to 6 and no values are changed. formula_143.
The variable formula_144 is chosen to be equal to 9 and no values are changed. formula_145.
The algorithm terminates.
Runtime.
After a preprocessing phase, the radius stepping algorithm can solve the SSSP problem in formula_146 work and formula_147 depth, for formula_148. In addition, the preprocessing phase takes formula_149 work and formula_150 depth, or formula_151 work and formula_152 depth.
References.
 ;templatestyles src="Reflist/styles.css" / ;