数学建模社区-数学中国
标题:
迪克斯特拉算法
[打印本页]
作者:
haibin969571154
时间:
2010-8-6 22:23
标题:
迪克斯特拉算法
%最短路问题(迪克斯特拉算法)
- L/ y7 L5 c% C2 U
clear;
& d' C* g$ h4 | S6 l
clc;
9 B+ [, q0 A+ p# G" U
M=10000;
- g) B0 l- ]; r
a(1,:)=[0,50,M,40,25,10];
$ P# C3 {$ M8 `2 l. M
a(2,:)=[zeros(1,2),15,20,M,25];
! d ?$ K+ \8 j6 l, z
a(3,:)=[zeros(1,3),10,20,M];
/ P+ \- S1 |! l
a(4,:)=[zeros(1,4),10,25];
, p0 n4 L k8 G% Q
a(5,:)=[zeros(1,5),55];
. u: l8 u7 [5 o# [% ~; U2 \8 K
a(6,:)=zeros(1,6);
" w6 L+ {6 K, g X5 O$ s4 X2 @; r
a=a+a';
\: v, u' V, Z$ G
%length函数返回的是矩阵中行数和列数中较大的长度
0 |( R+ \& g/ f# m# a, M( z
pb(1:length(a))=0;%生成一个一行多列的0矩阵
: T6 U0 O' j' I$ P4 m* O6 R8 \" l! d
pb(1)=1; %第一个数赋值为1
$ }1 h$ m) v7 D: w
index1=1;
, Y3 U5 @) ~9 r" Z: X P) D# f+ h
index2=ones(1,length(a));%生成一个一行多列的1矩阵
' j7 O' t' I# t# d' z: K) L2 a
d(1:length(a))=M; d(1)=0; temp=1;
/ ?0 V- v9 N" i/ g; O7 a- H
%sum函数为各行之和
( _" I3 [) L/ P) I+ S2 d
while sum(pb)<length(a)
( V7 p/ k5 N+ B
tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)
. t( _ e; d# i" r8 I3 a
d(tb)=min(d(tb),d(temp)+a(temp,tb));
' B8 t n c3 |8 K' q, m
tmpb=find(d(tb)==min(d(tb)));
9 \; u$ f* O3 c8 v$ w+ |
temp=tb(tmpb(1));
4 J) D/ }: e+ i! N* @& g
pb(temp)=1;
" a6 I- g2 U8 ]7 E. m* Z% Q) s0 e
index1=[index1,temp];
) [5 T/ `9 z+ Q8 C! v) z+ s
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
; ?. G9 a# x8 [4 L8 Y
if length(index)>=2
6 K+ ~! R1 c8 f; v$ d
index=index(1);
( \! [/ }$ Y& r9 S. h5 U
end
" Q, S" C) f. P3 Y: R
index2(temp)=index;
" V& ~% l' d/ h0 ~$ h
end
4 P1 ]% K0 I& q5 B/ |
d,index1,index2
5 ]% G; T0 n- O" u* T4 W1 ?' B) N
迪杰斯特拉算法用于求解一个有向图(也可以是无向图,无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题。算法构思很是巧妙(我这么认为),简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径,再到第二个点的最短路径,直至最后求解完成到第n个点的最短路径,而是求解从原点出发的各有向路径的从小到大的排列(如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了??!!),但是算法最终确实得到了从原点到图中其余各点的最短路径,可以说这是个副产品,对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后,理解算法本身就不是难题了。
+ w! Q0 G! o! e! X6 ^3 l
算法把一个图(G)中的点划分成了若干部分:
8 a$ g4 F: M5 l4 B7 f+ F
1):原点(v);
) E d0 {% u e. a3 Q2 A
2):所有周边点(C);
8 ]7 ?2 o1 E" a* ^: _
另外有一个辅助集合S,从v到S中的点的最短路径已经求得。S的最初状态是空集。
& v5 k. a o3 [% i1 ]$ l
这样就可以进一步划分图(G):
0 d' q( \; z8 x' T/ n2 x
1):原点(v);
: \! @- B7 d/ c$ n* ~3 c
2):已求出v至其最短路径的周边点(S);
1 U( T' N3 k7 x6 F
3):尚未求出v至其最短路径的周边点(Other=C-S);
6 j" k8 z# O: [2 W5 Q. z7 y
算法的主体思想:
, v S+ C1 g/ P. O: W
A、找到v——Other所有路径中的的最短路径vd=v——d(Other的一个元素);
: ^- j- E) q: G3 ~/ L2 E$ C
B、找到v——S——Other所有路径中的的最短路径vi=v——i(Other的一个元素);
; w7 ^% I$ Z0 ^3 H
C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除,否则将i加入S且从Other中删除。
; a- k0 j! g# w2 J a
重复以上步骤直至Other为空集。
n6 ^0 {7 G$ I K
" X" X9 G3 k' Z! Z& o
我们求得的最短路径是升序排列的,那为什么下一条最短路径就存在于v——
* I% \% ?) B- F' _; D
& O2 H+ b% I: N0 Q8 c3 b6 a0 E" N
作者:
紫辰
时间:
2010-8-6 22:37
程序没有错啊。你再看看吧
! B8 B+ C, e- h# |$ C
作者:
linmatsas
时间:
2010-8-6 22:43
回复
紫辰
的帖子
- f' s! A# u( m$ a/ ~9 y4 c
' ?' T3 G9 K! Y& h5 K0 ^% {
5 v: J! W1 D: _% U/ I1 T& \/ Q
我是说好像……人家在贴源程序吧…………
作者:
wajm_011
时间:
2010-8-7 09:03
看看
作者:
salad6
时间:
2010-8-26 11:33
试试运气啦~~~~~~~~~~~
作者:
queniao
时间:
2010-8-26 11:34
不错不错,我喜欢看
作者:
snrl
时间:
2010-8-26 11:35
楼主,你写得实在是太好了。我惟一能做的,就只有把这个帖子顶上去这件事了
作者:
chshfxfx
时间:
2010-8-26 11:36
顶顶更健康,越顶吃的越香。
作者:
icm
时间:
2010-8-26 11:38
顶顶更健康,越顶吃的越香。
作者:
libin1984
时间:
2010-8-26 11:46
哦~~
作者:
zhuneen
时间:
2010-8-26 13:52
楼主那种裂纸欲出的大手笔,竟使我忍不住一次次的翻开楼主的帖子……
作者:
huxiao9026
时间:
2010-8-26 18:59
哦~~
作者:
racheltong
时间:
2010-8-26 19:17
顶顶更健康,越顶吃的越香。
作者:
xphoenix
时间:
2010-8-27 00:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~
作者:
apple
时间:
2010-8-27 08:00
不错不错,我喜欢看
作者:
pcqsl
时间:
2010-8-27 12:00
顶顶更健康,越顶吃的越香。
作者:
nn58123
时间:
2010-8-27 15:00
声明一下:本人看贴和回贴的规则,好贴必看,精华贴必回。
作者:
yunwuya
时间:
2010-8-27 20:00
强烈支持。楼主万岁
作者:
dong241
时间:
2010-8-28 08:00
楼主的帖子实在是写得太好了。可是我立刻想到,这么好的帖子,倘若别人看不到,那么不是浪费楼主的心血吗?经过痛苦的思想斗争,我终于下定决心,牺牲小我,奉献大我。我要拿出这帖子奉献给世人赏阅,我要把这个帖子一直往上顶,往上顶!顶到所有人都看到为止!
作者:
周磊高
时间:
2010-8-28 12:00
我要把这个帖子一直往上顶,往上顶!
作者:
lwx193520
时间:
2010-8-28 15:00
强烈支持。楼主万岁
作者:
zjf822
时间:
2010-8-28 20:00
顶顶更健康,越顶吃的越香。
作者:
diaohaiq
时间:
2010-8-28 23:59
我要把这个帖子一直往上顶,往上顶!
作者:
collinssj
时间:
2010-8-29 08:00
不错不错,我喜欢看
作者:
srv2004
时间:
2010-8-29 12:00
试试运气啦~~~~~~~~~~~
作者:
casper
时间:
2010-8-29 15:00
我基本上是采用看英语文章的办法,先泛读,再精读,再一句一句看,最后再提纲挈领,总算是明白一点了,当然,也可能还是领悟错了。最后要说的一句话是:楼主,你很牛叉,希望你不是真的有病。
作者:
星际丑男
时间:
2010-8-29 20:00
强烈支持。楼主万岁
作者:
watermelon
时间:
2010-8-30 12:00
楼主的帖子实在是写得太好了。可是我立刻想到,这么好的帖子,倘若别人看不到,那么不是浪费楼主的心血吗?经过痛苦的思想斗争,我终于下定决心,牺牲小我,奉献大我。我要拿出这帖子奉献给世人赏阅,我要把这个帖子一直往上顶,往上顶!顶到所有人都看到为止!
作者:
liguoli
时间:
2010-8-30 15:00
楼主的帖子实在是写得太好了。可是我立刻想到,这么好的帖子,倘若别人看不到,那么不是浪费楼主的心血吗?经过痛苦的思想斗争,我终于下定决心,牺牲小我,奉献大我。我要拿出这帖子奉献给世人赏阅,我要把这个帖子一直往上顶,往上顶!顶到所有人都看到为止!
作者:
Hyacinth
时间:
2010-8-30 20:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~
作者:
weiye51
时间:
2010-8-31 08:00
呵呵 大家好奇嘛 来观看下~~~~
作者:
shtjwdw
时间:
2010-8-31 12:00
我要把这个帖子一直往上顶,往上顶!
作者:
ilava
时间:
2010-8-31 15:00
试试运气啦~~~~~~~~~~~
作者:
gpxsin
时间:
2010-8-31 20:01
顶顶更健康,越顶吃的越香。
作者:
greate
时间:
2010-9-1 08:00
来报道!!!!!!!!!!!
作者:
leah585
时间:
2010-9-1 12:00
声明一下:本人看贴和回贴的规则,好贴必看,精华贴必回。
作者:
yangxing1985
时间:
2010-9-1 12:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~
作者:
xiayulin
时间:
2010-9-1 15:00
顶顶更健康,越顶吃的越香。
作者:
xooe
时间:
2010-9-1 20:00
声明一下:本人看贴和回贴的规则,好贴必看,精华贴必回。
作者:
shinian1007
时间:
2010-9-2 12:00
楼主那种裂纸欲出的大手笔,竟使我忍不住一次次的翻开楼主的帖子……
作者:
天涯逸客
时间:
2010-9-2 15:00
我来了~~~~~~~~~ 闪人~~~~~~~~~~~~~~~~
作者:
jcccccccc
时间:
2010-9-2 20:00
试试运气啦~~~~~~~~~~~
作者:
WENCHANGJI
时间:
2010-9-3 12:00
(*^__^*) 指点系词……激扬文字……
作者:
tianaf
时间:
2010-9-3 15:00
留个脚印```````
作者:
peck
时间:
2010-9-3 20:00
我要把这个帖子一直往上顶,往上顶!
作者:
midlight007
时间:
2010-9-4 08:00
试试运气啦~~~~~~~~~~~
作者:
xbian
时间:
2010-9-4 12:00
来报道!!!!!!!!!!!
作者:
hbghr8187
时间:
2010-9-4 15:00
楼主的帖子实在是写得太好了。可是我立刻想到,这么好的帖子,倘若别人看不到,那么不是浪费楼主的心血吗?经过痛苦的思想斗争,我终于下定决心,牺牲小我,奉献大我。我要拿出这帖子奉献给世人赏阅,我要把这个帖子一直往上顶,往上顶!顶到所有人都看到为止!
作者:
belman
时间:
2010-9-4 20:00
鉴定完毕!
作者:
xinyu_1314_1981
时间:
2010-9-5 12:00
我要把这个帖子一直往上顶,往上顶!
作者:
leozzz
时间:
2010-9-5 15:00
顶顶更健康,越顶吃的越香。
作者:
liuguilong
时间:
2010-9-5 20:00
哦~~
作者:
淡然腊梅
时间:
2011-10-19 11:35
我顶啊顶顶
作者:
tanai
时间:
2011-10-24 15:58
顶顶更健康,越顶吃的越香。
作者:
alair002
时间:
2012-1-13 20:34
没有体力啦,资料能发给我一份吗?我的邮箱是18633525948圈163邮箱,谢啦
作者:
gaobuzheng
时间:
2012-1-15 19:20
作者:
WenqiSun
时间:
2012-2-3 19:11
代码写的很简洁,顶顶~~
作者:
Paul_Sing
时间:
2012-3-24 11:38
看看~~
作者:
HNzhangjie
时间:
2012-8-1 15:41
d,index1,index2
6 U$ q2 N/ A/ Z G _
问,求出来的分别是什么
作者:
sqirrel
时间:
2012-11-23 13:19
受用~~~~~~~~~~~··
作者:
623976603
时间:
2012-12-9 17:23
精辟!!!!!!!!!
作者:
yi_lip
时间:
2013-2-3 14:23
确实用matlab 写简洁,但是比其他的理解起来难一点。
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5