Optimizing the Bellman-Ford Algorithm Using GPU Parallelization

The Bellman-Ford algorithm’s temporal complexity of O(VE) renders it ineffective for big and dense networks, which is a serious computational disadvantage. The need for effective algorithms that can handle large-scale graph structures has increased due to the modern digital landscape’s rapid data expansion. The Single Source Shortest Path (SSSP) problem, which entails determining the shortest pathways from a single source vertex to every other vertex in a graph, is one of the most basic and extensively researched topics in graph theory. Numerous real-world applications, including biological network modelling, social media analysis, telecommunications routing, and navigation systems, are based on this issue. The Bellman-Ford algorithm stands out among the other algorithms created to address the SSSP problem because it can handle networks with negative weight edges and detect negative weight cycles, two features that more effective algorithms like Dijkstra’s do not allow. Our project investigates using Graphics Processing Units (GPUs) to parallelise the Bellman-Ford algorithm in order to get around this restriction. With thousands of cores, GPUs are made for extremely parallel calculations and provide significant speedups over conventional CPU-based processing for jobs that can be divided into discrete, independent work units. We developed a GPUaccelerated version of the Bellman-Ford algorithm by utilising NVIDIA’s parallel computing platform, CUDA (Compute Unified Device Architecture).