The Floyd-Warshall algorithm on graphs with negative cycles

DOI10.1016/j.ipl.2010.02.001zbMath1197.05143WikidataQ56170981 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

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

• 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.