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