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

释永思

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

& a1 S: Q. V1 O+ d我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
+ I' h' q' M# W, Y+ G原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
For j:=1 to n
+ s; ]* t! B" d4 v& x9 _8 o6 a( G9 KIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
: n4 j0 B4 y! Z3 ~' |/ X我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
# N( u) w& O# NFor j:=1 to n
( n: e; t' z+ B- X3 h9 a# K$ t/ c. \For i:=1 to n
- E( Y7 L! P% L$ `) `! `% EFor k:=1 to n
$ s( ~/ n3 e% I7 q) ]1 G2 M9 J' wIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% [. @& V$ x9 u& w- a# T我再改成如下形式，结果仍是正确的：
- f; C9 F6 d- ]5 e2 w$ yFor j:=1 to n
For i:=1 to j-1
5 A" u- ]4 O" C1 J5 C( ~3 `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];
& n, s$ H' c" j; E+ }1 y! F如果我改成如下形式，结果出错，不行了：
6 E, K# I- c" j4 iFor j:=1 to n
! @+ Z. X5 h6 K( IFor i:=j+1 to n
: I; W9 L  b3 R0 D' 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];
无法证明，只能用具体值来代入验证。

) @' D/ j  A# `! K' D9 n
6 B4 H/ V/ k7 v& V% w* u# }