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

释永思

关于弗洛伊德算法发现的怪现象：
' Z. D( Y# V9 ]0 b. i  S
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
, k( l/ K4 K( T& l3 y7 o7 `% h7 Q, w原来的弗洛伊德算法是：
4 F4 l8 ~% j5 v8 i- G8 {' hFor k:=1 to n
For i:=1 to n
, j$ m" q) l: y2 k  s* WFor j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
8 e' m9 k! }0 O. E/ k我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
" L, e) c; D( ?6 iFor j:=1 to n
For i:=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];
" l) f" w# @1 o- k: l( P& y! j我再改成如下形式，结果仍是正确的：
For j:=1 to n
For i:=1 to j-1
6 @4 {) J4 U1 h% q6 X2 o/ q/ f7 sFor k:=1 to n
+ _6 b/ j7 L3 _7 JIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
' E' O6 w$ t9 c  F! b2 HFor 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];
无法证明，只能用具体值来代入验证。


; t. O: R- X+ j7 _; x$ `