|
|
 |
| |
|
|
|
A Hybrid Bellman–Ford–Dijkstra (DB) Algorithm for Efficient Shortest Path Computation |
|
|
|
PP: 1059-1069 |
|
|
doi:10.18576/jsap/150407
|
|
|
|
Author(s) |
|
|
|
Aijaz Ahmad Magray,
D. Raju,
Aafaq A. Rather,
Ikram Ali,
Vidya Yerneni,
Ahmed A.F Osman,
Mohammed Ataelfadiel,
Ala Abdullah,
Maryam Nasser Almusallam,
Osman Elwasila Elshiekh,
Ali Salem Bin Sama,
P. Srinivasa Rao,
|
|
|
|
Abstract |
|
|
| In graph theory, detecting the shortest path between two active nodes remains a significant challenge in the research community. Finding the minimum-cost path between two nodes remains an important research problem with numerous practical applications. Although Dijkstra’s algorithm provides efficient shortest-path computation for graphs with non-negative edge weights and Bellman-Ford handles negative edge weights, neither algorithm simultaneously offers efficient computation, reduced search space, and low computational overhead. This limitation motivates the development of a hybrid algorithm that combines the strengths of both approaches while overcoming their individual weaknesses. In this paper, we propose a novel hybrid DB Algorithm that integrates the Bellman–Ford and Dijkstra algorithms to efficiently compute shortest paths in weighted graphs containing negative edge weights while reducing computational time and search-space complexity. The proposed DB Algorithm addresses the limitations of existing shortest-path algorithms by reducing computational overhead while efficiently handling negative edge weights and minimizing time and space complexity. The proposed algorithm is evaluated using two key performance metrics: Time to search for the Shortest Distance (TSSD) and computational space complexity. Experimental results demonstrate that the proposed DB Algorithm significantly reduces computational overhead while accurately identifying shortest paths in weighted graphs. Simulation results validate the effectiveness and computational efficiency of the proposed DB Algorithm. In the future, the proposed DB Algorithm has potential applications to wireless communication systems, network routing, multidirectional communication protocols, and quantum computing applications. |
|
|
|
|
|
|
|
