Hybrid Bellman-Ford-Dijkstra algorithm (Q511150)

The paper considers the single-source shortest paths problem in a digraph with negative edge costs allowed. A new, hybrid algorithm for finding shortest paths from a source \(s\) in a graph \(G\) with general edge costs is constructed by combining Bellman-Ford and Dijkstra algorithms (hence BFD algorithm). It improves the running time bound of Bellman-Ford for graphs with a sparse distribution of negative cost edges. This improvement is achieved by running Dijkstra at each Bellman-Ford round, without re-initializing values of distance function \(d\) at vertices. This is a legal implementation of Bellman-Ford, since Dijkstra is just a smart loop of relaxations. The authors prove the validity of this novel approach, despite the common knowledge: ``Dijkstra's algorithm cannot handle graphs with negative edge costs''. The bound for the number of BFD rounds is \(k + 2\), where \(k\) is the minimal integer such that for any vertex reachable from \(s\), there exists a shortest path from \(s\) to it containing at most \(k\) negative edges. The running time of a single BFD round is \(O(|E| + |V| \log |V |)\).