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

释永思

关于弗洛伊德算法发现的怪现象：
, |* V; i" {4 I$ \0 Z7 @: g
! m# \) t% b: E# E4 h4 M- T1 j" M我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
2 k3 `: U1 H3 _# i( l  \For i:=1 to n
( L% w4 d% }0 \For j:=1 to n
) x. {& `. U8 L! ~! CIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
3 D! p. G* \+ {- [* a我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For 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];
3 x' z5 O' d" S8 B$ F7 X  @我再改成如下形式，结果仍是正确的：
8 |/ P* M4 k5 F9 R: f. {0 m- B  g+ dFor j:=1 to n
For i:=1 to j-1
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];
7 {- Y$ i7 l% F7 O% ?4 b# K! `如果我改成如下形式，结果出错，不行了：
For j:=1 to n
For i:=j+1 to n
2 i1 ^6 s0 w" S6 L/ {; G0 l) C5 IFor k:=1 to n
- M  U. E) V. ?! L1 _If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
+ ~- V) b( [" z0 z& h3 j: `2 g2 W无法证明，只能用具体值来代入验证。
2 G: j5 @3 A" o5 }

# |9 @1 V6 [& U8 d/ Y