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

释永思

关于弗洛伊德算法发现的怪现象：
) @6 f& J7 F) P' S; S
+ q- _5 m- r# B; V( P7 Q我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
0 Y) ~# Y) U! f3 E  zFor 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];
( e8 o: b8 \1 Z# L. w4 p我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
6 g* e4 W6 a7 z2 g0 A3 i" D; hFor j:=1 to n
$ ?$ e5 d+ ~2 b# S: P# e: X6 ~3 o! eFor i:=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];
! [& Z9 ~& l9 L, @我再改成如下形式，结果仍是正确的：
2 c( a! z( X& D$ P* F2 J3 QFor j:=1 to n
8 t  T( d  m) x7 yFor i:=1 to j-1
! S1 ]: ?  I) k1 y  t3 GFor k:=1 to n
' M3 R6 u! P. D+ ]8 ]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
4 ]. c1 u' n4 d: m; xFor i:=j+1 to n
! \+ G! F% Y+ @5 y$ AFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
$ u1 K# q( _! ]$ l; L无法证明，只能用具体值来代入验证。
) f* f2 y  H3 d: v3 x7 D, _
, E7 M* g" h' h& e! b