数学建模社区-数学中国

标题: Floryd算法求解惑 [打印本页]

---

作者: shuidishenyu    时间: 2012-8-2 21:05
标题: Floryd算法求解惑
    在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
0 T  _% R1 h  V" H4 r  E    例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
& B6 k; b: i) ~                         0    50    inf    40    25    10
                         50    0    15    20    inf    25
0 t5 [- f! q, M( c; |- b5 ?                         inf    15    0    10    20    inf
                         40    20    10    0    10    25
/ o- O+ `+ p3 `                         25    inf    20    10    0    55
1 Y  a% A2 L2 P- x7 C) |6 G                        10    25    inf    25    55    0

    弗洛伊德算法:
# w2 z' O1 j! y2 m- v程序如下：
clear;
7 s( t. B1 `. Aclc;
6 B4 H% ^; |0 K5 ^M=10000;
. n! `7 C7 o! l3 N5 b+ E9 Ua(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
9 _+ X) h& F) i2 Wa(3,:)=[zeros(1,3),10,20,M];
$ @  H% Y$ N! }( f7 U6 C5 [7 E% |a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
/ b& F! g' H7 [- Z; f) ]5 e. X- N5 ja(6,:)=zeros(1,6);
b=a+a';path=zeros(length(b));
for k=1:6
! O, x1 d0 z1 b. b   for i=1:6
' H% q/ H$ `2 Q; j# P; J  D      for j=1:6
/ T, \! K; e  t         if b(i,j)>b(i,k)+b(k,j)
            b(i,j)=b(i,k)+b(k,j);
            path(i,j)=k;
# V" x; f. Z1 ]% A  Y         end
      end
9 }; g7 a/ l+ I6 B6 D1 i" L& h7 e8 w   end
2 f* H% y) L# S3 a- `4 Iend
/ o; L/ q  _7 f% X/ H9 a3 |b, path                  
运行结果：
b =
4 ]. \' Q; u5 J/ n1 i: Y/ m
1 m. }* v0 j+ a8 w( X- u     0    35    45    35    25    10
1 e$ [6 S5 h* y- F2 |1 A7 M4 w5 G    35     0    15    20    30    25
! X; |! g, C8 m) ~    45    15     0    10    20    35
    35    20    10     0    10    25
$ W1 p# }0 g! Z9 t4 d/ F    25    30    20    10     0    35
  o, i) s+ Q' d    10    25    35    25    35     0
2 ], [# x3 s" r) a) X
- j2 m7 D" _8 P1 k, [
9 L( z; g: W7 Bpath =
4 ]( v% U+ u4 t% f) [( f: ^/ N
/ I+ Y% z) A- v+ [9 W2 s) z     0     6     5     5     0     0
     6     0     0     0     4     0
     5     0     0     0     0     4
. ^- L7 C7 C6 w+ b. B     5     0     0     0     0     0
     0     4     0     0     0     1
# f$ j1 l) r$ l5 q; M) ?     0     0     4     0     1     0
% U4 b+ |! B& a1 u& o对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
# C7 X9 h, F% O/ X) [2 b0 j
$ b7 @% v! u+ p6 H& ~" |0 T            

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5