数学建模社区-数学中国
标题:
关于弗洛伊德算法发现的怪现象
[打印本页]
作者:
释永思
时间:
2016-4-21 17:00
标题:
关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象：
0 u: ~- m9 P" w0 J" _# }9 |7 F
% i1 B: }% z1 ?" c
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
2 N: L' D$ l G1 o0 H6 O' }
原来的弗洛伊德算法是：
5 W' ` z- ^( S- B0 g* I, \
For k:=1 to n
- W; u i+ e* [6 \: I9 G9 H( w" k
For i:=1 to n
. Z/ p5 s O/ d- P) f' Q; P; R
For j:=1 to n
i+ W$ v7 ]( N3 x0 g1 s
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
3 [( @, K9 X( ?4 d
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
' D- ]/ y3 t# T+ Z# h* K
For j:=1 to n
- ]( D+ v7 Y0 S/ i) c* _
For i:=1 to n
G( t* T4 H5 g# o+ T0 |
For k:=1 to n
' I! B _. H& a, h
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
; A5 Y! y( r, A" ~3 C
我再改成如下形式，结果仍是正确的：
3 c- P1 @$ P5 V2 y
For j:=1 to n
, V' H4 C2 j5 A* d- L+ C" Q
For i:=1 to j-1
3 q1 a4 V% T6 Q
For k:=1 to n
3 }, h0 w2 \$ p$ T2 y
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
0 Z5 M$ b/ T- o, Q: ]$ Y5 {7 [4 j
如果我改成如下形式，结果出错，不行了：
/ Z! t7 [" C! ~* D" z
For j:=1 to n
- E* A* ]0 I7 \6 Y# Y5 ^
For i:=j+1 to n
0 _" B% e; A/ h5 l( c* o7 ]& V, A% x
For k:=1 to n
* j& Z9 {7 P$ C k0 X3 g' j5 v. u
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
; v& i! q( V& ~7 }# i
无法证明，只能用具体值来代入验证。
' F( H+ J$ n( z8 J3 l1 d
/ Y9 d1 a9 ~7 z4 p8 x1 F
0 y5 e9 J2 c D, q) F& P
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5