cugraph icon indicating copy to clipboard operation
cugraph copied to clipboard

Implement MNMG Bellman-Ford algorithm to compute shortest paths in the presence of 0 and negative weights

Open ChuckHastings opened this issue 1 year ago • 1 comments

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.

ChuckHastings avatar May 14 '24 18:05 ChuckHastings

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

eriknw avatar Nov 27 '24 15:11 eriknw