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

释永思

关于弗洛伊德算法发现的怪现象：
) f- S7 P- v  B. C0 C
7 R$ g/ E# o9 \, q# O# g; H9 I我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
原来的弗洛伊德算法是：
For k:=1 to n
) |( @. `4 b0 LFor 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];
6 V3 M* c" W8 z$ x( f6 ~1 l" F我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
/ A: l/ X5 l5 p& R8 h" B: }! JFor j:=1 to n
- W3 J( M* ?) M# g5 c4 u9 r" A) T4 E) mFor i:=1 to n
  U# J0 W, o. IFor 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
For i:=1 to j-1
For k:=1 to n
' [1 e: H0 t8 N4 d$ NIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
1 ^5 u2 ^* f6 O9 z9 P1 p& ^: L; dFor j:=1 to n
For i:=j+1 to n
For k:=1 to n
5 u; p' H& T# E: z) d! K! o, HIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
( P$ ]( }$ _, i9 c无法证明，只能用具体值来代入验证。
& J1 Y5 J" q/ i) {3 D4 |7 o

  X; [4 a9 A% g8 m( W% Z& u0 j: \