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.

The key insight: 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 - thousands of threads processing edges simultaneously. Each thread relaxes one edge, using atomic operations to handle conflicts when multiple threads update the same node.

The tradeoff is always the same: sequential algorithms do minimum work, parallel algorithms do more work but spread it across processors. Which wins depends on the graph structure and how many processors you have.