Incorrect implementations of the Floyd--Warshall algorithm give correct solutions after three repeats

2019/04/02 by Ikumi Hide, Soh Kumabe, Hide, Ikumi +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1904.01210

arxiv created 2019/04/02 · arxiv updated 2019/04/03

Abstract

The Floyd--Warshall algorithm is a well-known algorithm for the all-pairs shortest path problem that is simply implemented by triply nested loops. In this study, we show that the incorrect implementations of the Floyd--Warshall algorithm that misorder the triply nested loops give correct solutions if these are repeated three times.

Related

• Improving The Floyd-Warshall All Pairs Shortest Paths Algorithm
• The Floyd-Warshall Algorithm, the AP and the TSP, Part II
• The Floyd-WarshallAlgorithm and the Asymmetric TSP
• The Floyd-Warshall Algorithm, the AP and the TSP III
• On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem