数学建模社区-数学中国

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

作者: haibin969571154 时间: 2010-8-6 22:23
标题: 迪克斯特拉算法
%最短路问题(迪克斯特拉算法)
clear;
clc;
M=10000;
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';
%length函数返回的是矩阵中行数和列数中较大的长度
pb(1:length(a))=0;%生成一个一行多列的0矩阵
pb(1)=1; %第一个数赋值为1
index1=1;
index2=ones(1,length(a));%生成一个一行多列的1矩阵
d(1:length(a))=M; d(1)=0; temp=1;
%sum函数为各行之和
while sum(pb)<length(a)
  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)
  d(tb)=min(d(tb),d(temp)+a(temp,tb));
  tmpb=find(d(tb)==min(d(tb)));
  temp=tb(tmpb(1));
  pb(temp)=1;
  index1=[index1,temp];
  index=index1(find(d(index1)==d(temp)-a(temp,index1)));
  if length(index)>=2
index=index(1);
  end
  index2(temp)=index;
end
d,index1,index2
迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。
   算法把一个图（G）中的点划分成了若干部分：
   1）：原点（v）；
   2）：所有周边点（C）；
   另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。
   这样就可以进一步划分图（G）：
   1）：原点（v）；
   2）：已求出v至其最短路径的周边点（S）；
   3）：尚未求出v至其最短路径的周边点（Other=C-S）；
   算法的主体思想：
         A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）；
B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）；
C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。
重复以上步骤直至Other为空集。

我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v——

作者: 紫辰 时间: 2010-8-6 22:37
程序没有错啊。你再看看吧

作者: linmatsas 时间: 2010-8-6 22:43
回复紫辰的帖子

我是说好像……人家在贴源程序吧…………

作者: 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
问，求出来的分别是什么

作者: sqirrel 时间: 2012-11-23 13:19
受用~~~~~~~~~~~··

作者: 623976603 时间: 2012-12-9 17:23
精辟!!!!!!!!!

作者: yi_lip 时间: 2013-2-3 14:23
确实用matlab 写简洁，但是比其他的理解起来难一点。

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