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

释永思

关于弗洛伊德算法发现的怪现象：
" v1 U8 l% W9 s0 }
& F( B1 z1 d3 e0 x我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
, [* ~4 v( F9 V$ ^; Z: F! X原来的弗洛伊德算法是：
) o( e% H- g4 r  ^4 jFor k:=1 to n
0 v! H( ?& b8 dFor i:=1 to n
- a, `- r5 Z( @8 zFor j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
  K$ A' \! m8 l; H) s, EFor j:=1 to n
For i:=1 to n
For k:=1 to n
* y& o+ v5 o* |# X, k# k  XIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
: L, N& Z/ v/ ]/ x. AFor j:=1 to n
! `0 A& N+ l) R" c' @1 `7 hFor i:=1 to j-1
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];
如果我改成如下形式，结果出错，不行了：
& o" l3 c# k8 O# C8 DFor j:=1 to n
1 y% _7 @& ]/ sFor i:=j+1 to n
For k:=1 to n
, M0 @) j# L* ]3 H1 A2 xIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
3 m! O- A9 l7 S8 W0 g& ?0 m无法证明，只能用具体值来代入验证。
% j0 f" o2 Q6 w" _/ L- D% o