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

Ikumi Hide, Soh Kumabe, Takanori MaeharaarXiv 2019 · arXiv

Abstract

The Floyd-Warshall algorithm is a cornerstone of graph theory, providing an $O(n^3)$ solution for the all-pairs shortest path problem. While the correct implementation requires a specific loop order (KIJ), common programming errors often lead to permutations like IJK or IKJ. This paper demonstrates that these "incorrect" versions are not fundamentally broken but merely slower to converge. We prove that repeating the IJK version three times, or the IKJ version twice, guarantees the correct shortest path distances for any graph without negative cycles.

Introduction

The simplicity of the Floyd-Warshall algorithm—three nested loops performing edge relaxations—belies the importance of their order. The standard algorithm iterates through intermediate vertices $k$ in the outermost loop (KIJ), ensuring that when calculating the distance between $i$ and $j$, all paths through vertices $1 \dots k$ have already been optimized.

In educational and professional settings, programmers frequently implement the loops in IJK or IKJ order. Conventionally, these are considered incorrect as they fail to find the shortest path in a single pass. However, this research explores the convergence properties of these permutations, showing that they eventually reach the optimal solution through repeated execution.

Methodology

The authors employ formal mathematical induction on path segments to analyze the behavior of misordered loops. They treat the algorithm as a sequence of edge relaxations: $d[i, j] \leftarrow \min\{d[i, j], d[i, k] + d[k, j]\}$.

The core of the proof relies on path decomposition. For the IJK permutation, a single pass identifies paths that are "upper unimodal"—where vertex indices in the path first increase and then decrease. By analyzing how these segments are "stitched" together in subsequent passes, the authors establish upper bounds on the number of repetitions required for full convergence.

To validate these bounds, the authors used exhaustive search to identify minimal counter-examples: the smallest graphs that fail to converge in fewer than the predicted number of passes.

Key Results

The study establishes two primary theorems regarding the convergence of misordered Floyd-Warshall implementations.

The IJK Permutation

Theorem 1 states that repeating the IJK algorithm three times is sufficient to solve the all-pairs shortest path problem for any graph without negative cycles. This bound is tight; Figure 1 illustrates a 7-node graph where two passes are insufficient to find all shortest paths.

Figure 1: A 7-node graph that serves as a minimal counter-example requiring exactly three repeats of the IJK algorithm to converge.

The IKJ Permutation

Theorem 2 establishes that the IKJ permutation requires only two passes to guarantee correctness. Figure 2 shows the minimal 4-node graph that requires a second pass to resolve all shortest paths.

Figure 2: A 4-node graph requiring exactly two repeats of the IKJ algorithm to reach the correct solution.

Discussion and Conclusion

While the "fixed" versions are 2x or 3x slower than the standard KIJ implementation, they remain within the $O(n^3)$ complexity class. This finding provides a theoretical "safety net" for developers: if the specific loop order is uncertain, running the procedure three times ensures a correct result.

However, several limitations remain. The proofs assume the absence of negative cycles, and the behavior of these repeated loops in detecting such cycles is not yet fully characterized. Furthermore, while theoretically interesting, the constant-factor slowdown makes this approach unsuitable for high-performance applications where the standard KIJ order should always be preferred. This work serves primarily as a pedagogical tool and a fascinating exploration of the robustness of relaxation-based algorithms.

Summary updated

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.
BibTeX
@misc{hide2019incorrect,
  author = {Ikumi Hide and Soh Kumabe and Takanori Maehara},
  title = {{Incorrect implementations of the Floyd-Warshall algorithm give correct solutions after three repeats}},
  year = {2019},
  eprint = {1904.01210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.01210},
}
Figure