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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
0 P$ A) q) q, b$ yFor i:=1 to n
For j:=1 to n
2 W5 h# Q& j- B, E8 mIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
$ @# X& Y  F; U5 V# U我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
2 D( T% a- r, N+ o1 W$ A3 ^" E; ^/ OFor i:=1 to n
/ _1 A- l' w& D5 I- z& \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];
. f8 b. O8 D4 c3 M+ g, B我再改成如下形式，结果仍是正确的：
For j:=1 to n
For i:=1 to j-1
+ q3 R' t6 \+ x# _$ ]3 BFor k:=1 to n
/ _: U* v9 T9 x% B* m) |0 K) OIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
/ J% y: R# L! v( q. V% m如果我改成如下形式，结果出错，不行了：
! `# Q7 D' f% UFor j:=1 to n
For i:=j+1 to n
' `0 c: T" ~- Y. r# wFor k:=1 to n
% z1 H* ]6 {  K3 \) k3 dIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。
) R- P- H- H8 c. W  r8 A
2 E3 t8 _7 a+ h7 g0 f