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

释永思

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

" t  }& M( Q6 f) p我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
0 s" @/ k* z- B! {7 y原来的弗洛伊德算法是：
For k:=1 to n
! {9 c" _$ l3 O  F8 D9 j) mFor i:=1 to n
For j:=1 to n
8 M( K& b$ e0 a0 C& S. hIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
# m+ U' \& A2 c! X, |0 @我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
6 A, R% d- e) H0 n3 K4 m8 `, S, v9 eFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
0 }$ w, q/ f4 h* M/ [  z+ e我再改成如下形式，结果仍是正确的：
For j:=1 to n
" b) J7 }4 m+ z7 p, |& A. d! Y( qFor i:=1 to j-1
7 Z0 a2 x! \3 l8 H/ tFor 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:=j+1 to n
. X( ]1 K" J  R. {( tFor k:=1 to n
/ s" Y; a8 ]* Z; \; k" iIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
1 e2 K7 B6 l% t无法证明，只能用具体值来代入验证。


8 B* ^  H' N2 P