数学建模社区-数学中国

标题: 迪克斯特拉算法 [打印本页]

作者: haibin969571154    时间: 2010-8-6 22:23
标题: 迪克斯特拉算法
%最短路问题(迪克斯特拉算法)
3 j! l% Z2 p4 bclear;5 v3 w! r& g: }: m4 a; J
clc;8 Z0 F0 S8 D: R! o* O( K$ E  i: O: ~
M=10000;/ i8 ?' ~: c' ~( x" a
a(1,:)=[0,50,M,40,25,10];
5 f* V  R: `; V) S5 p  @6 k8 k; r8 Fa(2,:)=[zeros(1,2),15,20,M,25];
- m( N8 M6 g2 ra(3,:)=[zeros(1,3),10,20,M];. ~2 F8 }2 p- c& t6 \1 s" K% `  w/ b
a(4,:)=[zeros(1,4),10,25];: \, o+ U0 c6 d  J; L& p
a(5,:)=[zeros(1,5),55];
+ }; V8 j/ I/ N$ s. |a(6,:)=zeros(1,6);
9 y2 W& _/ _' oa=a+a';* Y$ B  W* K9 P8 r: D7 U
%length函数返回的是矩阵中行数和列数中较大的长度
( K) e9 I  ~3 ]! H; l) w/ c1 V6 |pb(1:length(a))=0;%生成一个一行多列的0矩阵2 z# w# G$ Y+ ~/ @  c& }+ B1 \
pb(1)=1; %第一个数赋值为1* `. |$ }: m! ~. f3 H0 ]; O6 D* O
index1=1;
& R, J7 C" [; G7 T, s6 Windex2=ones(1,length(a));%生成一个一行多列的1矩阵" O" A7 G+ i2 \- {* I% M* q
d(1:length(a))=M; d(1)=0; temp=1;+ M6 ^, d6 c& C( b+ E; M9 k
%sum函数为各行之和, F7 v6 p% J) d1 U3 O# z
while sum(pb)<length(a), I2 F. K0 b# L- a" d
  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)' D2 ~5 t: j2 O! o- {- b
  d(tb)=min(d(tb),d(temp)+a(temp,tb));
  W4 T( R. c# O8 `( k" b  tmpb=find(d(tb)==min(d(tb)));, U# h3 A- f9 ^% U
  temp=tb(tmpb(1));+ ~7 ~/ g( Z5 P+ ?( c
  pb(temp)=1;
6 ^" y* ]& n/ N) g2 n  index1=[index1,temp];2 ]! X1 m8 F5 n
  index=index1(find(d(index1)==d(temp)-a(temp,index1)));& q' q6 u  b2 _9 [  L
  if length(index)>=2
- i! X" d" m/ @9 }" _3 `' i+ h    index=index(1);$ @) F( S+ R- v) z  y( y
  end
6 p' T9 L& j: Q4 S  index2(temp)=index;
9 q+ R& t6 Z: n/ q4 }: E) zend5 m( r/ K& q; E" ^) W$ B  v) Y- p
d,index1,index2* y: G0 Q5 A8 x" F6 s; H4 x  R7 x
迪杰斯特拉算法用于求解一个有向图(也可以是无向图,无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题。算法构思很是巧妙(我这么认为),简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径,再到第二个点的最短路径,直至最后求解完成到第n个点的最短路径,而是求解从原点出发的各有向路径的从小到大的排列(如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了??!!),但是算法最终确实得到了从原点到图中其余各点的最短路径,可以说这是个副产品,对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后,理解算法本身就不是难题了。: W, I' q0 ~& s1 W
       算法把一个图(G)中的点划分成了若干部分:
& |7 U' L7 x# d# \3 {6 x       1):原点(v);
) H! f' P! A, ]) i       2):所有周边点(C);
' B1 H+ M0 L5 S) b- K( Y1 n# t       另外有一个辅助集合S,从v到S中的点的最短路径已经求得。S的最初状态是空集。$ e0 @- }) _5 K+ l4 w/ F: Q
       这样就可以进一步划分图(G):9 `8 `$ V$ G4 o+ T. k
       1):原点(v);8 G; t9 k- v+ `. w" g* H+ W$ Q
       2):已求出v至其最短路径的周边点(S);
- V2 Y5 _5 j! @. B8 I4 C0 r) P       3):尚未求出v至其最短路径的周边点(Other=C-S);
# O# o2 g; J, V! M7 {  G       算法的主体思想:
9 O% v* x& `0 D           A、找到v——Other所有路径中的的最短路径vd=v——d(Other的一个元素);
) G+ e! h" R, {3 v+ z% k; ~% zB、找到v——S——Other所有路径中的的最短路径vi=v——i(Other的一个元素);
0 i4 ], q0 {1 D" n: h8 Q% A$ Y/ WC、比较vd和vi如果vd<=vi则将d加入S且从Other中删除,否则将i加入S且从Other中删除。
! P9 ^/ j, ?+ [重复以上步骤直至Other为空集。
0 }) ^' M) r- d( W4 r" A# e0 i* `2 Z1 r% o! ?4 o4 P' {9 M
我们求得的最短路径是升序排列的,那为什么下一条最短路径就存在于v—— ) t: b6 g: z% `& V. [8 y/ r  O* B; W
5 L% t3 e% ]. U7 t7 m# x

作者: 紫辰    时间: 2010-8-6 22:37
程序没有错啊。你再看看吧: k! o+ _4 S" d* y% m* m( U, Q% M

作者: linmatsas    时间: 2010-8-6 22:43
回复 紫辰 的帖子
5 f+ G- B7 l2 k/ z. R" f' {% ]
5 F4 z+ `$ `  u* ^  r5 r/ ]4 x. G( R6 X' m( t' V
    我是说好像……人家在贴源程序吧…………
作者: 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% ]7 R" [+ S/ l7 E+ P8 c
问,求出来的分别是什么
作者: 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