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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
+ g+ T+ B0 k; O3 g/ ZFor j:=1 to n
9 I: [0 r6 h- P& `3 }0 c0 ZIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
: B/ i! G; [" I+ Q我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
, S& }6 r) `' U) j% Z7 W$ LFor j:=1 to n
For i:=1 to n
+ r/ U& G8 T: F  [For k:=1 to n
9 o3 w- H# W: f' d) h1 [+ P: OIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% z& P0 J/ ~# l, e% c我再改成如下形式，结果仍是正确的：
For j:=1 to n
For i:=1 to j-1
% f4 S4 W$ _* I- M3 t% iFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
+ G% \% }2 y; G7 jFor j:=1 to n
$ Y: m3 a+ e6 u/ FFor i:=j+1 to n
For k:=1 to n
/ {+ w; M2 |% e0 l8 @9 _* eIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。
9 z2 C8 @5 G1 Q: M
* A! _1 |, z9 h. g. j$ M