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 s {\displaystyle s} 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 G = ( V , E ) {\displaystyle G=(V,E)} be a directed graph with | V | = n {\displaystyle |V|=n} nodes and | E | = m {\displaystyle |E|=m} edges. Let s {\displaystyle s} be a distinguished vertex (called "source") and c {\displaystyle 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 {\displaystyle v} reachable from s {\displaystyle s} , the weight of a minimum-weight path from s {\displaystyle s} to v {\displaystyle v} , denoted by dist ( s , v ) {\displaystyle \operatorname {dist} (s,v)} and abbreviated dist ( v ) {\displaystyle \operatorname {dist} (v)} . The weight of a path is the sum of the weights of its edges. We set dist ( u , v ) := ∞ {\displaystyle \operatorname {dist} (u,v):=\infty } if v {\displaystyle v} is unreachable from u {\displaystyle u} . Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; tent ( v ) {\displaystyle \operatorname {tent} (v)} is always ∞ {\displaystyle \infty } or the weight of some path from s {\displaystyle s} to v {\displaystyle v} and hence an upper bound on dist ( v ) {\displaystyle \operatorname {dist} (v)} . Tentative distances are improved by performing edge relaxations, i.e., for an edge ( v , w ) ∈ E {\displaystyle (v,w)\in E} the algorithm sets tent ( w ) := min { tent ( w ) , tent ( v ) + c ( v , w ) } {\displaystyle \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.
… excerpt ends here. Continue reading the full article.
