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

释永思

关于弗洛伊德算法发现的怪现象：
, |- V7 o) g! K2 N6 Z8 w; _
$ R. I0 K; a( W; y2 v( |8 m我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
" {+ L% Y% B4 D. \For k:=1 to n
) V9 V6 L2 ~4 r! \9 x$ N9 }' dFor i:=1 to n
For j:=1 to n
' ^: O+ i1 H5 R7 v( hIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% X6 d) @, Z" h2 u) M6 l我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
1 ?8 p$ `% R1 G0 Q( g3 a+ HFor k:=1 to n
4 }! D2 x1 o8 A; |( jIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
8 S' _" K: Y; h: O9 C& H9 h我再改成如下形式，结果仍是正确的：
# e5 X# E" `2 L' HFor j:=1 to n
For i:=1 to j-1
For k:=1 to n
: J( m: o3 y' }If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
& p" ]' ]- S+ B! e如果我改成如下形式，结果出错，不行了：
For j:=1 to n
0 S- T9 Q8 M5 p$ c7 v0 {) vFor 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];
无法证明，只能用具体值来代入验证。
/ m! y6 |" ^5 W/ S7 D
/ o" c/ w  G/ ]" v" E