The Floyd-Warshall algorithm on graphs with negative cycles
From MaRDI portal
Publication:991782
DOI10.1016/j.ipl.2010.02.001zbMath1197.05143WikidataQ56170981 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
05C35: Extremal problems in graph theory
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Optimum Experimental Design for Interface Identification Problems, Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles, Reconstruction of spatial data using isometric mapping and multiple-point statistics, Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks, Seven rules to avoid the tragedy of the commons, 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
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.