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

释永思

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

" M4 j% u, }( e1 M我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
4 h9 {+ R! E5 O6 w* F" s' ]原来的弗洛伊德算法是：
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];
9 `7 d9 g( `& w% I% B6 }; a# L6 h我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
$ s) I  q& O7 [# _" u8 s. d( h1 U% m' zFor k:=1 to n
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
7 Q; g. b" [. Z3 x3 zFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
! P" w' H/ }. H+ t! A/ P如果我改成如下形式，结果出错，不行了：
For j:=1 to n
For i:=j+1 to n
For k:=1 to n
& `) z6 _" r) C- g7 U. @& yIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
2 h9 H* c  r: s无法证明，只能用具体值来代入验证。
! r( O" b* S4 K) S1 ~
9 M) r, d# L5 X( g5 _6 O
# t) }  |- [1 r- ?$ l% M" \