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. Let formula_1 be a directed graph with formula_2 nodes and formula_3 edges. Let formula_4 be a distinguished vertex (called "source") and formula_5 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_6 reachable from formula_4, the weight of a minimum-weight path from formula_4 to formula_6, denoted by formula_10 and abbreviated formula_11. The weight of a path is the sum of the weights of its edges. We set formula_12 if formula_6 is unreachable from formula_14. Sequential shortest path algorithms commonly apply iterative labeling methods based on maintaining a tentative distance for all nodes; formula_15 is always formula_16 or the weight of some path from formula_4 to formula_6 and hence an upper bound on formula_11. Tentative distances are improved by performing edge relaxations, i.e., for an edge formula_20 the algorithm sets formula_21. For all parallel algorithms we will assume a PRAM model with concurrent reads and concurrent writes. 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_22. During each phase, the algorithm removes all nodes of the first nonempty bucket and relaxes all outgoing edges of weight at most formula_22. Edges of a higher weight are only relaxed after their respective starting nodes are surely settled. The parameter formula_22 is a positive real number that is also called the "step width" or "bucket width".