Parallelizing Bellman Ford Algorithm

Parallelizing Bellman-Ford Algorithm to solve Minimum Cost Flow Problem using GPU

We completed the parallelization of Bellman-Ford negative cycle algorithm with CUDA in order to use it in minimum cost flow problem solver. After gaining a deep understanding of algorithm we design a data structure in order to keep graph representation in such a way that it can be parallelized. We wrote segmented prefix algorithm for the relaxation part. On the parallel algorithm, we have used two strategies for the synchronization, i.e. explicit and implicit. When simulating the parallel algorithm, we have achieved a speed up of 2.2x when using explicit synchronization, and 2.9x when using implicit synchronization compared to sequential algorithm.