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

释永思

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

# y* _1 U0 j3 |# F6 A* {我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
! O; f, c* I, D& _- p3 z6 BFor k:=1 to n
For i:=1 to n
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];
9 O! H" {8 P) w3 H# T, h( y7 p我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
1 f1 N, t5 S$ |, K( V# Q( qFor j:=1 to n
" D# a, k4 w" \& qFor i:=1 to n
: f5 D7 ^0 c8 b6 ZFor k:=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 j-1
For k:=1 to n
/ j% Q2 d4 r& y1 [/ t8 N2 b! PIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
  u, G& @( O! U  @  f1 R+ N. TFor i:=j+1 to n
/ W' @' x# m1 rFor 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 |9 u( F. Z* f9 ?' |* Y5 Z1 X无法证明，只能用具体值来代入验证。


# V. ~3 N' r  p4 A