Yesterday at SRM 670 I got a funny story which I want to describe. During challenge phase I noted that one solution of medium problem in my room uses Floyd-Warshall. I thought "Oh, why haven't I thought about it during coding phase? Much shorter than those DFSes!", but then I noted that unexpectedly this infamous order of loops is not correct. It went like this:

FOR(x, n) FOR(y, n) FOR(z, n) dis[x][y] = min(dis[x][y], dis[x][z] + dis[z][y]);

while everyone should know that FOR(z,n) should be the outer loop, not the inner one. I tried to hack this solution, so I inputted graph 0-3-2-1, however my test was rejected, because problem was about trees and there was a constraint that parent of vertex i should be less than i and I didn't have time to come up with another testcase. Unexpectedly, this solution passed systests! I thought that its author is very lucky. However it turns out that for trees with this constraint this order of loop result in computing correct distances!

What we need to ensure is that we will somehow detect this one particular path during execution of that algorithm. With this order of loops it consecutively tries to compute distances dis[0][0], dis[0][1], ... dis[0][n — 1], dis[1][0], etc. in lexicographical order. Initialization consists of conditions dis[i][i] = 0, dis[x][y] = dis[y][x] = 1 iff <-> x-y is an edge. We will inductively (on lexicographical order) prove that it computes correct distances. Assume that x-y is not an edge.

Consider two cases:

1. y is not a descendant of x
   Let z be parent of x. We have z < x, so (x, y) > (z, y) (lexorder of pairs), so dis[z][y] was already computed and x-z is an edge, so both dis[x][z] and dis[z][y] are valid values, so we will detect that path when looking at z.
   
2. y is descendant of x
   Let z be parent of y. We have z < y, so (x, z) < (x, y), so dis[x][z] was already computed and z-y is an edge, so both dis[x][z] ad dis[z][y] are again valid values and we are done.

Funny how bugged version of Floyd-Warshall turns out to be correct on trees with this weird constraint on parents :P.