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

释永思

关于弗洛伊德算法发现的怪现象：
4 g6 d& Y+ R' }; t/ h; ]/ m
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
* c6 _3 I  a' o; w5 [原来的弗洛伊德算法是：
For k:=1 to n
* C" {9 @- }  f0 Z2 b, tFor i:=1 to n
For j:=1 to n
7 {' O2 M" q! o5 AIf 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
For k:=1 to n
8 N5 u% ~; N: Z- |4 u5 V9 kIf 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
* h; t# y% r6 _4 T) j- \For k:=1 to n
4 j& }- N( x) H$ MIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
9 p- Z& c+ i, v如果我改成如下形式，结果出错，不行了：
For j:=1 to n
: F1 g5 A% a$ x: i0 LFor i:=j+1 to n
. W( i8 C, _1 P+ @5 g: sFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。

  G% q" x) z, f! m8 Z
; }! T+ Z+ |3 C9 K$ P8 u+ l" t0 l