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

释永思

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

" w, _/ Q) E* V, A8 w我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
1 b6 O/ k5 J5 L: a, _2 D原来的弗洛伊德算法是：
1 s+ t6 ]. O- N0 lFor k:=1 to n
7 s  Z  A. u% s* @8 _4 }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];
" H- Q" E( ]  B: Z* ^) _我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
For j:=1 to n
) K, f$ e( m- J' T3 p! S3 AFor i:=1 to n
For k:=1 to n
* n2 ~8 o# ~$ J7 RIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
$ Q! `: T& {* s$ i) N; K2 N我再改成如下形式，结果仍是正确的：
; v3 F  j  E5 m  |1 @For j:=1 to n
For i:=1 to j-1
For k:=1 to n
/ i( G3 ~0 ^; W: y$ rIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
( F2 `( G$ B. t/ O) R+ P9 t( fFor i:=j+1 to n
For k:=1 to n
2 e! v2 |# J# SIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。


: t+ G: T# u% x) m- T" `* e0 w