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

释永思

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

: \  m& q2 Y  w' ]2 d9 Z5 }3 u我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
# Q& p, I- ?) [: s. g原来的弗洛伊德算法是：
( F% e- b: M2 r% fFor k:=1 to n
. U! D  b" T( `For i:=1 to n
3 J' V" T6 q8 |- l( \1 I  ?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];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
) a* ^7 k" B9 _For k:=1 to n
& k' _. t  S: V' Z8 a" L6 W  _If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
& U$ Y( F( C1 W/ zFor j:=1 to n
! _" |7 L) K3 w- lFor i:=1 to j-1
For k:=1 to n
# j' T' h' f/ ^1 [9 S- ?2 X$ G/ cIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% P0 M1 ~, U. |2 M3 P; R如果我改成如下形式，结果出错，不行了：
  j7 L. f1 Z0 ~' r% MFor j:=1 to n
& l5 w' }: N; i% U& AFor i:=j+1 to n
4 ?  ~' U# [, ]8 OFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。


& M" ?2 h7 _# a# x& d) r