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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
) Q% Z) v# R8 c7 P8 x' [原来的弗洛伊德算法是：
& l* X1 J8 P  M$ u7 {' [8 N' \For k:=1 to n
For i:=1 to n
For j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
; U# J) p& p5 ~  j! Y我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
0 i$ \) H- D7 w- P8 W$ E* E5 }5 B* HFor i:=1 to n
For k:=1 to n
' P  O; o0 L- v: IIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
" q- g+ J7 M9 fFor j:=1 to n
( }+ @. T' c3 H+ Q& y$ xFor i:=1 to j-1
4 m" i1 Q, W, p# H% \0 ^, H* {For k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% [4 V, x# N# e+ w! x: P如果我改成如下形式，结果出错，不行了：
4 }8 y& J3 M% Z! F+ X! G2 F  JFor j:=1 to n
$ m1 M1 h2 e/ EFor i:=j+1 to n
+ b" \8 x) n% |9 B$ t! O! WFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
, r0 d( L4 K, f# Y5 x. K无法证明，只能用具体值来代入验证。