数学建模社区-数学中国
标题:
Floryd算法求解惑
[打印本页]
作者:
shuidishenyu
时间:
2012-8-2 21:05
标题:
Floryd算法求解惑
在学习建模的过程中遇到一个关于floryd算法的问题，就是floryd所解出的结果并不一定能得出所有的结果。但自己无法求证，求正解。下面是一个例子：
! h% z9 I; m% T- @' H6 j) g* d
例13.2.某公司在六个城市 中有分公司，从 到 的直接航程票价记在下述矩阵的 位置上。（ 表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。
1 m8 i: m8 c7 r) @+ l' C6 A' W
0 50 inf 40 25 10
5 L3 ^: ]7 f# H1 C
50 0 15 20 inf 25
3 z% z: w7 S, X/ j: D$ T1 f7 c1 k
inf 15 0 10 20 inf
- f+ I. `! P% H0 M4 C1 e# B
40 20 10 0 10 25
% M! ^; @3 r7 f* j& g q' [
25 inf 20 10 0 55
8 r* e: _+ e; u7 ^7 g9 d* o$ e
10 25 inf 25 55 0
; A3 [0 A- H, k& c: w1 t! U+ s
* z. k, p/ b& y. L& X/ Z
弗洛伊德算法:
( C* F6 H4 D, g& O" G$ j4 w% l
程序如下：
1 a1 @% }) n) a) n
clear;
5 H% u" {6 d( Y( J; ~
clc;
: K Z5 ]. H" r9 o3 y
M=10000;
7 w6 P$ H' ]( y& {/ P2 H! S; _
a(1,:)=[0,50,M,40,25,10];
. p1 N5 @, O/ m2 B' D+ w: M9 B
a(2,:)=[zeros(1,2),15,20,M,25];
/ s* H9 `- I* X: u
a(3,:)=[zeros(1,3),10,20,M];
3 s- I8 O) u$ g- h( |
a(4,:)=[zeros(1,4),10,25];
" S" c- M3 [" T
a(5,:)=[zeros(1,5),55];
0 I. R) P* P. B* \6 Y9 m
a(6,:)=zeros(1,6);
8 _" I5 k% `+ O9 ^
b=a+a';path=zeros(length(b));
2 }6 u `7 s8 \" _ c7 J
for k=1:6
8 |! e* q$ K) v/ i: O# e" } T( o
for i=1:6
! ]3 R6 V" S. L' F5 v- G
for j=1:6
# d* B1 k& f7 z3 E' \! ~# i; g
if b(i,j)>b(i,k)+b(k,j)
( o0 Q5 F/ u A& y( c' z
b(i,j)=b(i,k)+b(k,j);
7 S4 D; }* X$ h8 ~- M8 L1 l
path(i,j)=k;
/ z/ F: h6 ]/ M; s+ q9 N6 q: ^5 m
end
' l. C# ?# }# P5 J: O6 l* f6 [
end
y3 b" T% U3 B: u( f, t, B
end
' A) ]4 z. U4 J3 A* k
end
8 R4 ^2 O2 Z( s3 y4 \& ^+ C
b, path
( a* c, P* v @7 g/ u" j3 G
运行结果：
7 T, F+ k9 Z- }. l0 u0 s& |/ S3 j
b =
" Z6 E+ f, |$ { F- w
6 i4 E" S3 Y9 U2 o& u5 d
0 35 45 35 25 10
# v- n1 u1 A5 W, W! s9 r$ B" l7 l
35 0 15 20 30 25
+ A# Z, X8 o `+ F }; [0 x9 s/ S& ], V
45 15 0 10 20 35
6 f/ P2 k5 g6 s
35 20 10 0 10 25
# }3 S2 P1 p2 {4 n/ \8 O$ ?
25 30 20 10 0 35
3 {# ~ |6 C% s+ i* }, v
10 25 35 25 35 0
& @) L* c3 d: r
* _, ^" V5 V4 ~
4 f1 c) n3 z( }. x* ^ k
path =
4 n" Y+ u. |) R. V5 U9 N( b$ q
5 }* G) d* o# \
0 6 5 5 0 0
/ H. F# v, O, V$ Q
6 0 0 0 4 0
( Y. S' \8 o$ L! u3 |
5 0 0 0 0 4
4 a% o, O- z1 g% L5 b
5 0 0 0 0 0
3 O$ J" y$ A( J( p
0 4 0 0 0 1
2 K* A! \, y8 p9 W5 r& l1 K- ]; F
0 0 4 0 1 0
% D3 w% S9 u3 i v/ K
对于从5到6，票价最少的路径有两条5--4--6和5--1--6，票价都为35元，但算法所得结果中这体现了5--1--6。
3 B# q& N/ f- E! _& g
; X& z; }3 e1 R3 S2 E' l
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5