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

释永思

关于弗洛伊德算法发现的怪现象：
( ]% S* o# u9 L+ ^& t" ?: U9 T
; f' O: R! q! [我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
$ ?8 j# v" l0 M3 H7 _原来的弗洛伊德算法是：
' U7 k8 Z5 `5 O6 M( u8 sFor k:=1 to n
For i:=1 to n
  P  {; P, O& H9 r: lFor j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
. i$ n* T' f: Y$ @! @% CFor j:=1 to n
' b/ U: Q! w. U; j# rFor i:=1 to n
! t* b0 \( S& I$ TFor k:=1 to n
+ O7 Q8 E4 I0 Y% S. }/ p8 xIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
  u/ n7 x3 b: n# g( |% w我再改成如下形式，结果仍是正确的：
+ U1 @: R  M8 hFor j:=1 to n
For i:=1 to j-1
For k:=1 to n
" b% n( |( H8 }3 G, }3 uIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
7 d4 O8 ?1 e; t" _7 nFor j:=1 to n
. b6 o) }8 u9 |* I; ]For i:=j+1 to n
! t9 }1 V( S; u! D4 A2 ^For k:=1 to n
) \+ ]5 K' z8 J% ^4 J1 b( UIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
6 x$ U. ]* x8 n$ U2 f' F; S) L6 F无法证明，只能用具体值来代入验证。
$ S8 v* ^" x( V- ?) d5 N! F

- K: @7 \: Y' ~; I: r- ^+ M