Health & Environmental Research Online (HERO)


Print Feedback Export to File
6229619 
Journal Article 
Hybrid Bellman–Ford–Dijkstra algorithm 
Dinitz, Y; Itzhak, R 
2017 
Elsevier 
42 
Elsevier 
35-44 
We consider the single-source shortest paths problem in a digraph with negative edge costs allowed. A hybrid of the Bellman–Ford and Dijkstra algorithms is suggested, improving the running time bound of Bellman–Ford for graphs with a sparse distribution of negative cost edges. The algorithm iterates Dijkstra several times without re-initializing the tentative value d(v) at vertices. At most k+2 iterations solve the problem, if for any vertex reachable from the source, there exists a shortest path to it with at most k negative cost edges. In addition, a new, straightforward proof is suggested that the Bellman–Ford algorithm produces a shortest paths tree. 
Algorithm; Shortest path; Negative edge