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

释永思

关于弗洛伊德算法发现的怪现象：
8 m5 K0 |( u4 h: F. E3 k
. H) j8 Y; S. [4 l- n! r; O我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
" H1 ~6 e9 f8 _& J5 J/ y+ p* y原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
5 l: u  G2 g/ i" P/ ?, ~For j:=1 to n
6 ?6 ~" H) _$ L' M# h4 @/ |If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
% Z. a7 @' j/ @For i:=1 to n
' d# r% B& a3 kFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
% j: B0 A8 I# B/ C9 s$ RFor j:=1 to n
2 @" S. w. ]8 b2 ~  R* c7 ^  @# O+ o6 \For i:=1 to j-1
For k:=1 to n
  p. y; E5 D( G/ RIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
8 d3 X# H, h) P如果我改成如下形式，结果出错，不行了：
/ E, {( W8 Z1 @3 }For j:=1 to n
For i:=j+1 to n
For k:=1 to n
- H  ~. d5 ]! n' m& y" q/ ~8 ~$ A" OIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。
/ V& b/ X$ W3 s' {/ F7 v- w
* o0 y$ |- w5 t; w' [0 ~8 M