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

释永思

关于弗洛伊德算法发现的怪现象：
5 |5 N, v7 Y4 v7 G1 W: D9 T2 ?
$ E2 K# C6 `+ g1 j- ]我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
, F; A' a! ^+ s! |原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
For j:=1 to n
$ D* F% l! s' \  J0 {# CIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% E4 d/ y( s: w/ D( p我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
- v, x" K  J1 g" K9 SFor i:=1 to n
& D( \" i) c- u- j7 dFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
0 O* Q2 G9 U5 Y, s我再改成如下形式，结果仍是正确的：
For j:=1 to n
For i:=1 to j-1
For k:=1 to n
4 r1 e: {5 W# r2 XIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
/ k- d8 G  g. i- p% E( k* eFor j:=1 to n
For i:=j+1 to n
1 t4 B- O, w% M& Y) S+ PFor k:=1 to n
" E8 M0 J- @- E. uIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。

1 I7 Y) F, {: y( L