数学建模社区-数学中国

标题: Floryd算法求解惑 [打印本页]
作者: shuidishenyu    时间: 2012-8-2 21:05
标题: Floryd算法求解惑
    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
" P- |& G2 D" |  ^: L( _; Z    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。0 t! M4 d  J6 [3 u
                         0    50    inf    40    25    10/ m: Z0 B) e1 D1 l: y" ~1 y& }
                         50    0    15    20    inf    25 - h/ F  l7 _& ^8 O5 v
                         inf    15    0    10    20    inf
! x  T+ {5 b" V" Y. {7 n                         40    20    10    0    10    25
: o1 [) \; r. B1 Z  x! _$ u                         25    inf    20    10    0    55+ I3 L2 C% d& O$ P3 V; A
                        10    25    inf    25    55    0
4 l4 A/ U5 O9 C7 W  Q
3 \9 f. U( E) f, W    弗洛伊德算法:$ H/ K. u# t9 D3 U  ]" S
程序如下：
* k% t" t4 M; O' N8 O/ Sclear;3 W2 A6 Z. o/ V+ q7 Y
clc;
& T2 N& N0 g. \) p1 o7 a7 w, i' GM=10000;2 l% e* g0 J7 F
a(1,:)=[0,50,M,40,25,10];
5 j+ @" k3 ?7 N! f2 ya(2,:)=[zeros(1,2),15,20,M,25];
1 x7 X0 R2 _' c& R' m$ \a(3,:)=[zeros(1,3),10,20,M];
# _! @7 `% h$ z' g  B* {5 Oa(4,:)=[zeros(1,4),10,25];) G0 A$ X, t/ I4 v
a(5,:)=[zeros(1,5),55];8 I( f, G* J8 X+ P
a(6,:)=zeros(1,6);/ m+ x' l: C. }' n4 D
b=a+a';path=zeros(length(b));, x) W) k; n: C: y1 X3 `1 O% N
for k=1:6
9 V9 N, |6 j4 A   for i=1:6) n- n( N5 L6 ]. d7 r1 N; l
      for j=1:6; r# q9 O8 R# B& ^% [: u7 s
         if b(i,j)>b(i,k)+b(k,j)
! N# h6 l; {% V0 h! @/ t5 o, `            b(i,j)=b(i,k)+b(k,j);
* {* D) J* \1 A% k& b6 j+ X            path(i,j)=k;/ h# f( E' S2 m4 ]7 |" p
         end. x7 A' O8 B* |  e8 s6 T" B
      end
# A- v/ T6 ~, C" }- i/ y   end2 p' ~6 u  k1 s, I
end
3 L! J& G$ }$ S4 ?# M: }b, path                  ' P5 u+ G+ l8 E0 R) ^+ d9 @
运行结果：
9 @" h6 {/ K& ^2 _# Yb =
' i' A. P, e, @- d5 `, W- L0 U0 Z
; R  z6 P. [4 R1 X7 }$ u3 l     0    35    45    35    25    10' ]' V& X  z' S! N, t  J2 f
    35     0    15    20    30    25
0 N6 y/ `& T/ V" j( g8 O    45    15     0    10    20    35
5 h) G7 V9 K, L2 K    35    20    10     0    10    25
; h. y2 o) t! L4 O! B    25    30    20    10     0    35
) P% v8 L. v6 j9 D! ^, g    10    25    35    25    35     0- X- R/ s+ T2 H" N4 F- @

) I5 ?+ p: ?, Q8 `' |, W- x) Z' Z: U5 v7 X$ l
path =! q  U( R" C4 y) g
$ j# l* D2 r8 {6 U4 Y
     0     6     5     5     0     04 t: t& ^# ]- T
     6     0     0     0     4     0  v2 F( p/ H: h3 U$ N1 \4 n
     5     0     0     0     0     4% a+ X, P  ^- }5 R: C
     5     0     0     0     0     0. h* \+ s' h- b  I- R$ t( o- @2 W
     0     4     0     0     0     1
* ]5 P8 L5 \5 Y) b     0     0     4     0     1     0" H4 K8 G3 v9 O& ?1 A
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。( C% z# u4 m' N. N2 I& H
/ o* N" z3 q1 C4 K( U+ q9 }
            



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5