The Floyd-Warshall algorithm on graphs with negative cycles

DOI10.1016/J.IPL.2010.02.001MaRDI QIDQ991782zbMATH OpenOpenAlexWikidataFDO

Authors 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

graph algorithmsdesign of algorithmsFloyd-Warshall algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Recommendations

• Negative-cycle detection algorithms
• Negative-cycle detection algorithms
• scientific article; zbMATH DE number 3958733
• Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem
• Finding all the negative cycles in a directed graph

Cites work

• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• scientific article; zbMATH DE number 839551 (Why is no real title available?)
• A new approach to all-pairs shortest paths on real-weighted graphs
• A new upper bound on the complexity of the all pairs shortest path problem
• A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths
• A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• An O(n 3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths
• 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
• Combinatorial optimization. Theory and algorithms.
• Computing and Combinatorics
• More algorithms for all-pairs shortest paths in weighted graphs
• New Bounds on the Complexity of the Shortest Path Problem

Cited in

(14)

• Algorithms – ESA 2005
• scientific article; zbMATH DE number 3958733 (Why is no real title available?)
• Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
• Seven rules to avoid the tragedy of the commons
• Reconstruction of spatial data using isometric mapping and multiple-point statistics
• High-level synthesis of DSP applications using adaptive negative cycle detection
• Combining VNS with genetic algorithm to solve the one-to-one routing issue in road networks
• Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
• MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
• Finding all the negative cycles in a directed graph
• Optimum experimental design for interface identification problems
• Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem
• Multi-manifold discriminant Isomap for visualization and classification
• Switched max-plus linear-dual inequalities: cycle time analysis and applications

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: The Floyd-Warshall algorithm on graphs with negative cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991782)