Hm wait floyd-warshall is subtly different from regular matrix multiplication with (+, *) replaced with (min, +). We're accumulating into the existing matrix s

Hm wait floyd-warshall is subtly different from regular matrix multiplication with (+, *) replaced with (min, +). We're accumulating into the existing matrix so the order of loop iteration matters, it has to be {k, i, j}. As such I'm not sure how C_ij := \min_k (A_ik + B_kj) would work to give all pairs shortest path, since in floyd-warshal the results of C[i][j] at iteration k depend on C[i*][j*] for k-1 being computed, which is not true for the above where C_ij can be computed independently of all others. It seems like it _is_ possible to easily express APSP via an inner product with (min, +), but it's less efficient than floyd warshal. Whereas floyd warshall asks "What's the shortest path from i to j using vertices in {1..k}", if you instead ask "what's the shortest path from i to j of length at most k" and then use repeated-squaring you can get the answer in n^3 lg(n). See http://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module4/all_pairs_shortest_paths.xhtml http://users.cecs.anu.edu.au/~Alistair.Rendell/Teaching/apac... https://cse.buffalo.edu/~hungngo/classes/2004/531/notes/floyd-warshal.pdf https://cse.buffalo.edu/~hungngo/classes/2004/531/notes/floy... https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss1... https://www.cs.utexas.edu/~ecprice/courses/randomized/fa15/notes/lec14.pdf https://www.cs.utexas.edu/~ecprice/courses/randomized/fa15/n...*