The Floyd-Warshall algorithm on graphs with negative cycles
From MaRDI portal
Publication:991782
DOI10.1016/j.ipl.2010.02.001zbMath1197.05143OpenAlexW2031407623WikidataQ56170981 ScholiaQ56170981MaRDI QIDQ991782
Publication date: 7 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.02.001
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (7)
Reconstruction of spatial data using isometric mapping and multiple-point statistics ⋮ Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks ⋮ MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles ⋮ Multi-manifold discriminant Isomap for visualization and classification ⋮ Seven rules to avoid the tragedy of the commons ⋮ Optimum Experimental Design for Interface Identification Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- A new upper bound on the complexity of the all pairs shortest path problem
- A new approach to all-pairs shortest paths on real-weighted graphs
- A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- More algorithms for all-pairs shortest paths in weighted graphs
- New Bounds on the Complexity of the Shortest Path Problem
- Computing and Combinatorics
- An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
- Combinatorial optimization. Theory and algorithms.
This page was built for publication: The Floyd-Warshall algorithm on graphs with negative cycles
