Hybrid Bellman-Ford-Dijkstra algorithm
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 |)\).
- A hybrid algorithm for TSP
- On the optimality of Bellman-Ford-Moore shortest path algorithm
- A heuristic improvement of the Bellman-Ford algorithm
- A hybrid algorithm for a class of vehicle routing problems
- Randomized Speedup of the Bellman–Ford Algorithm
- An improvement on fixed order Bellman-Ford algorithm
- (Incremental) priority algorithms
- A generalization of Dijkstra's algorithm
- A Note on Dijkstra's Shortest Path Algorithm
- A Shortest Path Algorithm for Edge-Sparse Graphs
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- Application of a technique for research and development program evaluation
- Buckets, Heaps, Lists, and Monotone Priority Queues
- Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- Introduction to algorithms
- Models of greedy algorithms for graph problems
- Scaling Algorithms for the Shortest Paths Problem
- Shortest path feasibility algorithms: an experimental evaluation
- Undirected single-source shortest paths with positive integer weights in linear time
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- Improvement and experimental evaluation on classical Bellman-Ford algorithm
- An improvement on fixed order Bellman-Ford algorithm
- Dijkstra-based algorithms for the shortest path problem with edges of negative length
- The shortest-path and bee colony optimization algorithms for traffic control at single intersection with Networkx application
- An efficient alternative strategy for finding prices in envy-free perfect matchings
This page was built for publication: Hybrid Bellman-Ford-Dijkstra algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511150)
