Skip to main content

General-Weight SSSP (Bellman-Ford)

Problem Specification#

Input#

G=(V,E)G=(V, E), an unweighted graph, and a source, sVs \in V. The input graph can either be undirected or directed.

Output#

Output: DD, a mapping where D[v]D[v] is the shortest path distance from ss to vv in GG and \infty if vv is unreachable. If the graph contains any negative-weight cycles reachable from ss, the vertices of these negative-weight cycles and vertices reachable from them must have a distance of -\infty.

Algorithm Implementations#

The code for our implemenation is available here. We provide more details about our implementation in [1].

Cost Bounds#

The algorithm runs in O(Diam(G)m)O(\mathsf{Diam}(G)m) work and O(Diam(G)logn)O(\mathsf{Diam}(G) \log n) depth. Please [1] for details.

Compiling and Running#

The benchmark can be compiled by running:

bazel build -c opt //benchmarks/GeneralWeightSSSP/BellmanFord:BellmanFord_main

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

numactl -i all ./bazel-bin/benchmarks/GeneralWeightSSSP/BellmanFord/BellmanFord_main -s -m -src 1 inputs/rMatGraph_J_5_100

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

numactl -i all ./bazel-bin/benchmarks/GeneralWeightSSSP/BellmanFord/BellmanFord_main -s -c -m -src 1 inputs/rMatGraph_J_5_100.bytepda

References#

[1] 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.