Parallel Single-Source Shortest Path

Single-source shortest path finds the shortest path from one node to all others in a graph. Dijkstra’s algorithm is the classic solution, but it’s inherently sequential. For large graphs, you need parallel approaches.

Bellman-Ford is easier to parallelize than Dijkstra. It works by repeatedly relaxing all edges until no improvement is possible. Each pass is independent. You can split edges across processors and relax them in parallel, then synchronize.

The downside: $O(V \cdot E)$ work even in the best case, vs Dijkstra’s $O(E \log V)$. You trade efficiency for parallelism.

Delta-stepping is designed specifically for parallel execution. It groups vertices into “buckets” by their tentative distance, then processes buckets in phases. Within a bucket, relaxations can happen in parallel. The delta parameter controls the bucket width. Smaller delta means more parallelism but more phases.

Most graph algorithms have dependencies that limit parallelism. You can’t know the next nearest node until you’ve processed the current one. Delta-stepping and similar algorithms relax this by doing slightly more work than necessary in exchange for better parallel scaling.

GPU approaches go further, with thousands of threads processing edges simultaneously. Each thread relaxes one edge, using atomic operations to handle conflicts when multiple threads update the same node.

Which approach wins depends on the graph structure and how many processors you have.