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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
4 ~: |% c; L9 k4 n! _For i:=1 to n
& [( i! ?5 V% _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];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
' ?3 n0 V& I( I& C* CFor j:=1 to n
: |1 E! W7 b! w+ F( eFor i:=1 to n
, F, w5 H4 y4 G( T7 _% }; \( fFor k:=1 to n
: e0 D8 f/ M8 }( E: {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:=1 to j-1
: ^6 X1 I9 t! j1 p4 R6 K% b$ u' o2 P6 aFor k:=1 to n
" c2 X- q" t' X6 tIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
; Q- Y. F, c4 ~) p; k  h7 l8 iFor i:=j+1 to n
: L1 R; L& U, e/ cFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。

# {& N9 I( \& R