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

释永思

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

- c1 W1 s; [$ V. q4 S! T我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
4 P4 G5 |; {* T$ |原来的弗洛伊德算法是：
For k:=1 to n
6 P% C1 |8 |- f, ]0 RFor 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];
' v9 K" j/ o1 g" t& q$ Y我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
6 o$ k" R0 f* X2 G7 q( jFor j:=1 to n
$ B# r; ]5 x# o! ~" i1 PFor i:=1 to n
% j  B$ g/ _7 m1 O8 f2 d$ |% P* R( P* kFor k:=1 to n
. R7 s( {/ P6 l. D9 B( |If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
' f2 d) |% D& I7 EFor j:=1 to n
) v8 O  e3 h/ J! P8 W/ Y2 hFor i:=1 to j-1
For k:=1 to n
# r- ?: X, \/ Z+ d- r6 @If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
$ j6 l: T, @5 \$ M0 p# u% q% \5 X如果我改成如下形式，结果出错，不行了：
For 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];
无法证明，只能用具体值来代入验证。

6 I7 e' }; X, |6 w: t( Y
: h: x/ T* K$ b. _/ \5 ~, v# u