数学建模社区-数学中国

标题: Floryd算法求解惑 [打印本页]
作者: shuidishenyu    时间: 2012-8-2 21:05
标题: Floryd算法求解惑
    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
( o+ D" `) N; F0 P    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。; V7 `- h9 F( R% h
                         0    50    inf    40    25    10# p: K# _4 e3 |3 ]3 U! t
                         50    0    15    20    inf    25 ) B7 i; p/ i+ V6 K
                         inf    15    0    10    20    inf1 D4 n8 e7 _) o% L+ k
                         40    20    10    0    10    25
9 b; r5 p- r! X                         25    inf    20    10    0    55
$ R. }7 {' f4 E: y                        10    25    inf    25    55    0
' Y% m9 W% ]1 W1 Z0 }& h5 ^6 _9 R% k, K1 W' v/ T' h4 ^2 V1 Z' o
    弗洛伊德算法:
, I* d  D" D% \5 J程序如下：
: }* D- n9 b- G) K& A7 wclear;8 a+ W- J/ U0 V9 h- p
clc;
& z- ~1 Y5 |; t3 H9 i. LM=10000;  U6 |% E( I% I0 m8 I
a(1,:)=[0,50,M,40,25,10];
) \( S0 W5 A( L, |/ da(2,:)=[zeros(1,2),15,20,M,25];
& t" G, _: Z! U: e  A- Y" ca(3,:)=[zeros(1,3),10,20,M];' c' P; A! a' e: l! R  v6 Z
a(4,:)=[zeros(1,4),10,25];
" ~7 _+ i, b# g. [. [  h# C0 Ta(5,:)=[zeros(1,5),55];
. e' }! n- b% |; T" wa(6,:)=zeros(1,6);* @1 d$ J1 u/ e, w
b=a+a';path=zeros(length(b));) e* n; ]5 k& r' t7 v% ?. w
for k=1:6. d4 p' Z* w- \  h- }1 d% d0 K
   for i=1:6
9 a2 \8 }0 x7 E4 k# W1 |$ \      for j=1:6
' E9 l2 P7 Y8 K         if b(i,j)>b(i,k)+b(k,j)
# D3 m! L, p  O" {            b(i,j)=b(i,k)+b(k,j);' S& K1 B+ [/ O: Q
            path(i,j)=k;" [; a7 i) F! G+ P
         end/ d+ h; I) E1 [! l. {8 p5 F$ Y+ u  q
      end- b5 l) p/ r- [" e; g2 z+ q
   end# J9 G. f1 U1 ?- h2 c- n* X* r
end) j7 n/ K7 b) L3 N% b; X; a3 t9 n- j
b, path                  0 b2 O0 c$ U+ X
运行结果：: m+ t  ~7 h  s( R! N  \" K
b =
' b! g; |% [6 s
" _% d9 ~1 f( I     0    35    45    35    25    10
0 C# Z& }5 S* D+ e% D    35     0    15    20    30    25
; v5 n# t& d2 p# j# I5 K* a* X    45    15     0    10    20    35
7 N2 c9 Z, S6 a0 W8 B, U    35    20    10     0    10    256 y) H0 S4 j3 Z/ n
    25    30    20    10     0    353 }) `$ Z' J: O$ e
    10    25    35    25    35     0
# Z7 ^4 d  J! O% P5 H: M- Z& G; u$ U! I
- L; x# l! A) t* h
path =* F  [3 B0 t5 w: v

0 o5 _- H; o1 D- j     0     6     5     5     0     0( I  x: D+ G* n2 v8 ]' F+ b/ S
     6     0     0     0     4     0
% J" G  H: e. `" @! Z+ a* ^# q- T3 Q+ \     5     0     0     0     0     4" D! P$ G) b/ y: e4 `7 L1 K9 ^
     5     0     0     0     0     04 ]0 j  w9 F. {, T0 I
     0     4     0     0     0     14 `0 i( h& H1 u- b
     0     0     4     0     1     0
4 T) _" z8 W& T$ m( _+ w对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。; U1 B- B( f/ \$ z8 }0 m& s' b/ ~' C

5 c3 @1 a  P: I2 o9 G8 H; L/ J# l$ G            



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