The Floyd-Warshall Algorithm, the AP and the TSP

2001/11/29 by Howard Kleiman, Kleiman, Howard
Biochemistry, Genetics and Molecular Biology · Business, Management and Accounting · Computer Science · Decision Sciences · Mathematics · #Auction Theory and Applications #Combinatorics (math.CO) #Consumer Market Behavior and Pricing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Genome Rearrangement Algorithms #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.math/0111309

Text in Word 2000, math in MathType 4.0, sent in a PDF file written in Acrobat 5.0, 23 pages

arxiv created 2001/11/29 · openalex publication_date 2001/11/29 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We use admissible permutations and a variant of the Floyd-Warshall algorithm to obtain an optimal solution to the Assignment Problem. Using another variant of the F-W algorithm, we obtain an approximate solution to the Traveling Salesman Problem. We also give a sufficient condition for the approximate solution to be an optimal solution.

Citations

• Hamilton Circuits in Graphs and Directed Graphs

Related

• The Floyd-Warshall Algorithm, the AP and the TSP, Part II
• The Floyd-WarshallAlgorithm and the Asymmetric TSP
• A Method for Solving Traveling-Salesman Problems
• The Asymmetric Traveling Salesman Problem
• Using a Hamiltonian cycle problem algorithm to assist in solving difficult instances of Traveling Salesman Problem