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

释永思

关于弗洛伊德算法发现的怪现象：
, i$ e5 E* t' D4 i! q
% y) k8 ~* x4 k3 U& b0 X$ E我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
For i:=1 to n
6 H8 P; o2 M: S& Z# K6 CFor j:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
' r& t  T) \: J" U* g0 I9 t* X7 EFor j:=1 to n
$ u; c. o5 }, e* ~: d7 t5 hFor i:=1 to n
For k:=1 to n
. J1 y2 S2 E! f+ C6 S7 VIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
8 O+ e6 A; `2 l- Q& w我再改成如下形式，结果仍是正确的：
; s4 H% b) G, g5 p" X/ ~2 SFor j:=1 to n
6 R1 m( a! @. V; wFor i:=1 to j-1
0 ^! U$ ], E/ ^/ E# iFor k:=1 to n
+ U. ~  m: _$ X# ]If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
. B' w: ^3 v  H1 v# E+ K如果我改成如下形式，结果出错，不行了：
# E: N8 G9 ^: [% [For j:=1 to n
For i:=j+1 to n
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];
5 @. n1 Q/ B4 W3 j- e- O/ b, B无法证明，只能用具体值来代入验证。

2 K5 D; Q3 P$ w# f