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

释永思

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
- u& T! e+ V6 s& m" z4 sFor 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];
& v2 T3 Q2 q. ~5 o. V9 C1 f: D我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
7 h' u5 Z- s# Z3 c: E  @For j:=1 to n
' s% ]1 F: A  u) z0 z+ eFor i:=1 to n
% `; j) L  Q" ?8 p+ sFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
( P$ _& N4 M/ Y0 M# F7 h, r我再改成如下形式，结果仍是正确的：
) X9 t4 }% E4 Y2 BFor j:=1 to n
For i:=1 to j-1
" t- C8 g* |9 f; C0 p) `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];
+ C) ?$ ]/ b! k7 _2 ?3 \4 w& \如果我改成如下形式，结果出错，不行了：
) a6 ^  I8 Q) s& l8 \' ZFor j:=1 to n
For 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];
无法证明，只能用具体值来代入验证。


& A# l9 }7 {; _" v  \3 F