The Floyd-Warshall algorithm on graphs with negative cycles

DOI10.1016/j.ipl.2010.02.001zbMath1197.05143OpenAlexW2031407623WikidataQ56170981 ScholiaQ56170981MaRDI QIDQ991782

Stefan Hougardy

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

zbMATH Keywords

design of algorithmsgraph algorithmsFloyd-Warshall algorithm

Mathematics Subject Classification ID

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

• Algorithm 97

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