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

释永思

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

) \- @9 @3 D5 r( J4 \2 X1 ?我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
' W* T) C2 r) Q$ X5 ZFor j:=1 to n
/ d; T! a; m4 |) I0 QIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
( u/ ~, t6 r/ W! _0 Y我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
5 |0 [$ ?7 D! C% t9 ?5 d6 XFor i:=1 to n
7 @# F& f4 r; z7 N7 T7 G% iFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
& r, s; P$ y3 z( b" }For j:=1 to n
For i:=1 to j-1
" L$ ~* Z: H2 ]2 bFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
* D- K% H. e/ ?' uFor j:=1 to n
/ L/ ~% w0 i/ X+ l' `2 e$ pFor i:=j+1 to n
( d2 o" D+ I$ D9 v4 n& B, WFor k:=1 to n
$ n( p# `' E: X6 PIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
* j8 d7 U  h1 M无法证明，只能用具体值来代入验证。

' C- y7 B  Y3 `: \% c, Y
5 ^1 E% ?6 r# e# b