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

释永思

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

( h- P+ X& a4 Z3 m/ b5 P我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
, c3 l8 X( k* _% v- A原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
For j:=1 to n
9 m1 h+ G( X, L7 ~! A6 ~5 yIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
& E8 f2 A% R# R) m7 L4 f我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
  S3 F# G$ N, c+ U  r6 rFor 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];
我再改成如下形式，结果仍是正确的：
$ q6 d' U7 X9 W" ?For j:=1 to n
4 r0 v) F" K* Y" x& k  t& y' L0 f& iFor i:=1 to j-1
( i- I/ ^# k, X; Z/ ^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];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
0 m# O# v, p4 c, jFor 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];
无法证明，只能用具体值来代入验证。
% B) ~1 j  e# ^. ^$ a0 {2 F# \
+ U4 t% E- P& R, i3 |/ \" M9 z
: H  \" i! @5 o  N$ |6 u8 W