Hybrid Bellman-Ford-Dijkstra algorithm

详细信息    查看全文

• 作者：Yefim Dinitz ; ^{dinitz@cs.bgu.ac.il} ; Rotem Itzhak ^{rotem.itzhak@gmail.com}
• 关键词：Algorithm ; Graph ; Shortest path ; Negative edge
• 刊名：Journal of Discrete Algorithms
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：42
• 期：Complete
• 页码：35-44
• 全文大小：352 K
• 卷排序：42

文摘

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)d(v) at vertices. At most k+2k+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.