cugraph
cugraph copied to clipboard
Implement MNMG Bellman-Ford algorithm to compute shortest paths in the presence of 0 and negative weights
Our current shortest path implementation uses delta stepping to parallelize Dijkstra's algorithm efficiently on the GPU.
Dijkstra's algorithm requires all edges to have positive weights. In order to support weight 0 edges and negative weight edges we need to implement the Bellman-Ford algorithm.
This issue is to provide a C++ implementation of Bellman-Ford.
Dijkstra's algorithm requires all edges to have positive weights. In order to support weight 0 edges and negative weight edges we need to implement the Bellman-Ford algorithm.
The GraphBLAS implementation of SSSP in LAGraph uses delta stepping, and it supports negative weights. See for instance: https://github.com/GraphBLAS/LAGraph/blob/afeb9dffca463fb966f1d9637986af55b04df461/src/algorithm/LAGr_SingleSourceShortestPath.c#L364-L376