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

释永思

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

; Y! `- H( _0 m: q我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
; u% `" p, W3 ~) F原来的弗洛伊德算法是：
( Q: C9 ]2 D9 I( a! S' @6 G5 B2 L# dFor k:=1 to n
0 Z0 t) r# M( S2 N3 J5 QFor i:=1 to n
For j:=1 to n
' j: E% t; ]' R7 B9 qIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
* b8 u( G( H7 [+ ?$ G, _我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
2 e6 t) F7 p, v) Y1 DFor j:=1 to n
, I' o/ G$ ?( ]* ^- Z' N" F" yFor i:=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];
( e2 q) V4 A4 ^1 K6 i# v- _+ b我再改成如下形式，结果仍是正确的：
) a, `' s+ R& N6 w8 o, FFor j:=1 to n
For i:=1 to j-1
  E1 W+ R9 c+ UFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
( n1 c5 V' L2 U) Z9 l! q如果我改成如下形式，结果出错，不行了：
3 f9 V8 _# Q4 W  iFor j:=1 to n
For i:=j+1 to n
For k:=1 to n
5 }& a1 t% y1 b# U% ^+ \, B4 JIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
0 x# c9 z2 P( N* C无法证明，只能用具体值来代入验证。
8 `0 X/ Z+ i+ ~% s1 a3 e2 F' O. z
0 M5 x) d3 q/ h4 w& q+ h