数学建模社区-数学中国
标题:
关于弗洛伊德算法发现的怪现象
[打印本页]
作者:
释永思
时间:
2016-4-21 17:00
标题:
关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象：
; v* s5 x3 g( {- D
' k+ l, Y% Y8 c- @5 F# A: M! @/ A
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
8 f2 W/ S$ K3 M1 W3 N5 j9 Y
原来的弗洛伊德算法是：
* v& ?% ^& B: s3 U9 K, E
For k:=1 to n
- _; K$ c7 o% Y# \. A
For i:=1 to n
0 g: l5 z! i: @
For j:=1 to n
3 |/ h* b: `- l( Z
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
. j6 S( x+ W0 W, ?
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
* z Q. J j8 {' }/ s6 X
For j:=1 to n
; P6 x1 D5 X' X9 g, ]. `# E! L% J
For i:=1 to n
0 S7 [" K% L0 ?' F; _* y
For k:=1 to n
6 o n8 g8 q% _3 V, q' |
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
- ]2 g. D4 D, i2 I0 S
我再改成如下形式，结果仍是正确的：
; x7 n" n8 g# x. ?) x k4 `
For j:=1 to n
* o5 O) X6 L3 ]0 [: W7 r" ^9 {
For i:=1 to j-1
% ]* o# h* m. d2 [$ _4 ]! V" H
For k:=1 to n
: o: v6 f @* `, I& n/ c
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
, W: Q/ J( g0 |$ T3 y
如果我改成如下形式，结果出错，不行了：
- r$ ]4 d9 d( U6 E; `
For j:=1 to n
% t% y/ _; r% t& n: R% M8 f1 `
For i:=j+1 to n
% i! m" H! O% {8 E* A8 `6 R; p x
For k:=1 to n
+ S p4 ]4 o |3 Q9 e! x
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
: ~6 C9 Y3 i0 Y6 A2 ~$ Y/ R2 w
无法证明，只能用具体值来代入验证。
& O6 ^) g q6 ?3 l8 `, k/ M1 B2 f
I; n9 Y7 d6 I5 N
# _' |6 N% `8 n/ O; f9 C
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5