Delta Stepping
Delta Stepping (Parallel shortest path search on a graph)
Delta-stepping is a natural parallelization of dijkstra's algorithm. It uses the ideas of 'buckets', each with a width of delta in order to exploit parallelism available in the input-graph. Just as in dijkstra, each vertex has a tentative distance, or tent(v). This represents the best cost to get to a vertex v, from s. Each vertex v belongs in the bucket corresponding to tent(v)/delta.
The algorithm processes each bucket sequentially. When we first begin processing a bucket, all vertices are added to a 'frontier', F. We then iterate over all outnghs of F, and see if we can shorten the distance to them (i.e. reduce tent(v)). This is just the 'relax' step in dijkstra's algorithm, just applied in parallel to all adjacent vertices. Note that some relaxations can affect vertices already in our current bucket, while others can 'drop' vertices in subsequent buckets to the current bucket. Some relaxations (over 'heavy' edges, i.e. edges with weight > delta) cannot make a neighbor move into the current bucket, so we save these for the end of processing the current bucket.
One way to think about the algorithm visually is that we center ourselves at the source vertex, s and explore the graph in concentric rings (the precise word for this is annulus, but you know it's a funny kind of word) around s, each with a width of delta. Within an annulus we run bellman-ford, but between annulus's we are running dijkstra. When delta=1 the algorithm is identical to dijkstra and when delta=\infty it is identical to bellman-ford.