Parallel single-source shortest path algorithm

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 path between every pair of vertices in a 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 $G=(V,E)$ be a directed graph with $|V|=n$ nodes and $|E|=m$ edges. Let $s$ be a distinguished vertex (called "source") and $c$ 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 $v$ reachable from $s$, the weight of a minimum-weight path from $s$ to $v$, denoted by $\operatorname {dist} (s,v)$ and abbreviated $\operatorname {dist} (v)$. The weight of a path is the sum of the weights of its edges. We set $\operatorname {dist} (u,v):=\infty$ if $v$ is unreachable from $u$.

Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; $\operatorname {tent} (v)$ is always $\infty$ or the weight of some path from $s$ to $v$ and hence an upper bound on $\operatorname {dist} (v)$. Tentative distances are improved by performing edge relaxations, i.e., for an edge $(v,w)\in E$ the algorithm sets $\operatorname {tent} (w):=\min\{\operatorname {tent} (w),\operatorname {tent} (v)+c(v,w)\}$.

For all parallel algorithms we will assume a PRAM model with concurrent reads and concurrent writes.

Radius stepping algorithm

For the radius stepping algorithm, we must assume that our graph $G$ 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 $r:V\rightarrow \mathbb {R} _{+}$. The algorithm visits vertices in increasing distance from the source $s$. On each step $i$, the Radius-Stepping increments the radius centered at $s$ from $d_{i-1}$ to $d_{i}$ , and settles all vertices $v$ in the annulus $d_{i-1}<d(s,v)\leq d_{i}$.

Following is the radius stepping algorithm in pseudocode:

    Input: A graph $G=(V,E,w)$, vertex radii $r(\cdot )$, and a source node $s$.
    Output: The graph distances $\delta (\cdot )$ from $s$.
 1  $\delta (\cdot )\leftarrow +\infty$, $\delta (s)\leftarrow 0$
 2  foreach $v\in N(s)$ do $\delta (v)\leftarrow w(s,v)$, $S_{0}\leftarrow \{s\}$, $i\leftarrow 1$
 3  while $|S_{i-1}|<|V|$ do
 4  | $d_{i}\leftarrow \min _{v\in V\setminus S_{i-1}}\{\delta (v)+r(v)\}$
 5  | repeat   
 6  | | foreach $u\in V\setminus S_{i-1}$ s.t $\delta (u)\leq d_{i}$ do
 7  | | | foreach $v\in N(u)\setminus S_{i-1}$ do
 8  | | | | $\delta (v)\leftarrow \min\{\delta (v),\delta (u)+w(u,v)\}$
 9  | until no $\delta (v)\leq d_{i}$ was updated
 10 | $S_{i}=\{v\;|\;\delta (v)\leq d_{i}\}$
 11 | $i=i+1$
 12 return $\delta (\cdot )$

For all $S\subseteq V$, define $N(S)=\bigcup _{u\in S}\{v\in V\mid d(u,v)\in E\}$ 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 $d_{i}$ is decided on each round with the goal of bounding the number of substeps. The algorithm takes a radius $r(v)$ for each vertex and selects a $d_{i}$ on step $i$ by taking the minimum $\delta (v)+r(v)$ over all $v$ in the frontier (Line 4).

Lines 5-9 then run the Bellman-Ford substeps until all vertices with radius less than $d_{i}$ are settled. Vertices within $d_{i}$ are then added to the visited set $S_{i}$.

Example

Example graph

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 $\delta$ in the pseudocode.

All neighbors of A are relaxed and $S_{0}=\{A\}$.

Node	A	B	C	D	E	F	G
Tentative distance	0	3	$\infty$	5	3	$\infty$	3

The variable $d_{1}$ is chosen to be equal to 4 and the neighbors of the vertices B, E and G are relaxed. $S_{1}=\{A,B,E,G\}$

Node	A	B	C	D	E	F	G
Tentative distance	0	3	6	5	3	8	3

The variable $d_{2}$ is chosen to be equal to 6 and no values are changed. $S_{2}=\{A,B,C,D,E,G\}$.

The variable $d_{3}$ is chosen to be equal to 9 and no values are changed. $S_{3}=\{A,B,C,D,E,F,G\}$.

The algorithm terminates.

Runtime

After a preprocessing phase, the radius stepping algorithm can solve the SSSP problem in ${\mathcal {O}}(m\log n)$ work and ${\mathcal {O}}({\frac {n}{p}}\log n\log pL)$ depth, for $p\leq {\sqrt {n}}$. In addition, the preprocessing phase takes ${\mathcal {O}}(m\log n+np^{2})$ work and ${\mathcal {O}}(p^{2})$ depth, or ${\mathcal {O}}(m\log n+np^{2}\log n)$ work and ${\mathcal {O}}(p\log p)$ depth.