Skip to main content

Single-Source Widest Path

Problem Specification#

Input#

G=(V,E,w)G=(V, E, w), a weighted graph with integral edge weights, and a source, sVs \in V. The input graph can either be undirected, or directed.

Output#

DD, a mapping where D[v]D[v] is the maximum over all paths between ss and vv in GG of the minimum weight on the path and \infty if vv is unreachable.

Algorithm Implementations#

We provide two implementations of the algorithm, one based on the weighted SSWidestPath algorithm, and the other based on the Bellman-Ford algorithm. We note that the Bellman-Ford implementation works for the version of this problem where the graph has general edge-weights. The code for our implemenation is available here.

Cost Bounds#

The wBFS-based implementation runs in O(n+m)O(n + m) expected work and O(Diam(G)logn)O(\mathsf{Diam}(G) \log n) depth w.h.p. The Bellman-Ford based implementation runs in O(Diam(G)m)O(\mathsf{Diam}(G)m) work and O(Diam(G)logn)O(\mathsf{Diam}(G) \log n) depth.

Compiling and Running#

The benchmark can be compiled by running:

bazel build -c opt //benchmarks/SSWidestPath/JulienneDBS17:SSWidestPath

It can then be run on a test input graph in the uncompressed format as follows:

numactl -i all ./bazel-bin/benchmarks/SSWidestPath/JulienneDBS17/SSWidestPath_main -s -m -src 1 inputs/rMatGraph_J_5_100

It can then be run on a test input graph in the compressed format as follows:

numactl -i all ./bazel-bin/benchmarks/SSWidestPath/JulienneDBS17/SSWidestPath_main -s -c -m -src 1 inputs/rMatGraph_J_5_100.bytepda

References#

[1] Laxman Dhulipala, Guy Blelloch, and Julian Shun
Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 293-304, 2017.

[2] Laxman Dhulipala, Guy Blelloch, and Julian Shun
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 393-404, 2018.