关于弗洛伊德算法发现的怪现象

释永思

关于弗洛伊德算法发现的怪现象：
0 i& ?- z% e1 ?; D
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
For j:=1 to n
5 k2 H( Y3 v/ j8 dIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
For k:=1 to n
! z2 p7 j8 _) s! hIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
! B( d( Z( J  t* P: t7 v. W9 x我再改成如下形式，结果仍是正确的：
For j:=1 to n
$ f9 @7 I+ i8 ?1 p2 L5 YFor i:=1 to j-1
8 ]6 n; c- j: o; {2 ~6 ?/ uFor k:=1 to n
& t  K9 O. i7 H$ vIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
: X, A) |4 H* E4 }/ B& [9 wFor i:=j+1 to n
. B/ s+ g4 l0 B1 o7 B# U1 sFor k:=1 to n
# S) w1 s( a- ?0 K1 `+ ~If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。

3 x. t) W& ~  v' I/ `  {: v2 W