Optimizing the Bellman-Ford Algorithm Using GPU Parallelization

Download 13
File Size 413.39 KB
File Count 1
Create Date 12/05/2025
Last Updated 12/05/2025

Download

Description

Optimizing the Bellman-Ford Algorithm Using GPU Parallelization

Dr. Raman Cholla , Rahul Ranjan Kumar, P Jayanth Reddy, Ansh Vajpai, Ashutosh Kumar

JAIN (Deemed-to-be University)

Department of Computer Science and Engineering

ABSTRACT

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).

Keywords
Computer Unified Device Architecture (CUDA), Graphics Processing Units (GPUs), and the Single Source Shortest Path (SSSP) problem.

Previous

Optical Fiber Communication

Next

SMS Spam Detection Using Machine Learning and Deep Learning Techniques

What is DOI

DOI:

A DOI will help Author(s) easily locate a document from your citation. Think of it like a Social Security number for the article you're citing — it will always refer to that article, and only that one. While a web address (URL) might change, the DOI will never change.

Where can i find DOI:

In IJSREM journal articles, the DOI will be printed with the article itself, usually on the footer of the page
If the DOI isn't included in the article, look it up on the website CrossRef.org (use the "Search Metadata" option) to check for an assigned DOI.

Benefits:

Allows for a quick and precise search.
Article can always be located.
Persistent link to its location on the Internet.
Easier identification of published articles even if the metadata URL is changed.
Aid in citation tracking, ensuring a researcher has accurate metrics on how and where their research outputs are being used or referenced.

Site Map

Terms and Conditions

Copyright Infragmentation

Publication Ethics

Editorial Board

Processing Fee's

Call for Papers

Publication Procedure

Research Topics

Frequently Asked Questions

What type of papers does International Journal of Scientific Research in Engineering and Management (IJSREM) publish?

Research Paper, Survey Paper, Informative Article, Case Studies, Review Papers, Comparative Studies

How long does it take for an accepted paper to be actually published?

Approximate will inform within 24 hours via email and sms.

What is the procedure to submit my paper?

Please Submit your Research Paper here Submit Research Paper Online - IJSREM

What is a Paper ID?

Paper ID is an Unique Identification Code provided to your submitted Manuscript. You should always mention the Paper ID during any communication with us.

How long my published paper will stay online?

Lifetime.

May I submit more than one article?

We will accept multiple submissions across multiple communities, as long as the author joins each community.

Why IJSREM?

IJSREM is one of the world's leading and fastest-growing research publications with the paramount objective of discovering advances by publishing insightful, double-blind, peer-reviewed scientific journals.

Publication Time Period

The Submitted Article/Paper will accept within 12-24 Hours, and it can publish within 24 Hours

Publication Procedure

Manuscript Submission - Check Manuscript Plagiarism - Send for Editorial Review - Final Decission to Author - Payment of Publication Fee - Re-screening - Final Publication

Processing Fee's

For Management, Hosting & Office Expenditure IJSREM Journal may charge some amount to publish the paper.

To Publish a Paper ₹: 800/- INR (without DOI)

₹:1000/- INR (with DOI)

To the extent possible under, Indospace Publications has waived all copyright and related or neighboring rights to Journal. This work is published from India.

Disclaimar Privacy Policy Terms and Conditions

Copyright © 2023. All Rights Reserved