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

释永思

关于弗洛伊德算法发现的怪现象：
+ _+ t$ \: i" Q9 d* Y
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
) V1 V- |, q2 q+ ~" h/ k, G  V$ M3 }原来的弗洛伊德算法是：
. O% n2 y3 D# l6 B/ i. `For 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];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
& K/ n! u0 p4 m% z# N. tFor j:=1 to n
For i:=1 to n
+ n; j, ~- b. z3 xFor 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
' j: U1 ]8 \7 D4 o/ b9 Q3 HFor i:=1 to j-1
/ @2 y  `! T  q  EFor k:=1 to n
; A: p5 j0 B0 Y* @( F' r* jIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
1 Y, h4 `  v- \! c6 u/ H& ^* LFor j:=1 to n
$ e# ]" D# l% V8 E4 yFor 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];
无法证明，只能用具体值来代入验证。


% g+ M, e0 V- q