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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
$ u& W; x! @( U% b* ]7 o原来的弗洛伊德算法是：
For k:=1 to n
8 f) i% s+ H9 ], UFor i:=1 to n
* w) l! Z; I8 Z: _/ ^For j:=1 to n
( I3 m- o0 L' ^( P+ iIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
2 U% d- n( A8 w4 u; l+ l我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
& z- U" I) r4 V4 [  D5 _For j:=1 to n
, C5 u- X+ Y2 O& g$ W. ]For i:=1 to n
: X  ?5 m2 h, ?# Z2 Z/ KFor k:=1 to n
4 B: \) d. N+ r1 k% `2 C8 aIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
$ a! r1 U; I0 V  ]# s8 wFor j:=1 to n
For i:=1 to j-1
For k:=1 to n
* y3 Z3 w7 x5 `+ h, `6 ?$ ?If 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:=j+1 to n
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];
无法证明，只能用具体值来代入验证。
% u7 l( N5 l* R2 o0 i

4 s: }' O* E" E: l/ S7 P