A NOTE ON THE OPTIMALITY OF SOME ALL-SHORTEST-PATH ALGORITHMS
Mario Nakamori · 1972
It is proved that any algorithm that determines the shortest distances between all node pairs in a network by repeated applications of the so-called triple-operations should contain at least n(n-1)(n-2) such operations, where n is the number of nodes in the network. Hence, FIoyd's algorithm [2J, as well as Dantzig's [lJ and Katayama and Watanabe's [5J, has been shown to be optimal.