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

释永思

关于弗洛伊德算法发现的怪现象：
* b3 W* u5 k+ o+ @. P
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
4 R8 `' w) z) Y2 c* O3 p. u原来的弗洛伊德算法是：
8 P5 Z5 _& Q! b, I; G$ TFor k:=1 to n
# i$ x; W0 W& uFor i:=1 to n
For j:=1 to n
. @( U  T3 E2 M; N1 b) TIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
3 N+ l- _- M5 l7 [) K( t我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
For i:=1 to n
6 {6 N! g( `! U' V: R6 x- q' O$ QFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
" T$ ]- k9 p, }  K) q3 r我再改成如下形式，结果仍是正确的：
For j:=1 to n
: T4 ^5 Y6 S. s# g7 cFor i:=1 to j-1
+ o# x" n) T& U# TFor k:=1 to n
' Q  g3 @) n8 ?5 y  }$ ZIf 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:=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];
% \& \6 V, [$ ?$ I9 ?无法证明，只能用具体值来代入验证。
4 W( x# `' P5 Z

5 D* ^5 @( M! X6 v% H