QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 25886|回复: 61
打印 上一主题 下一主题

迪克斯特拉算法

[复制链接]
字体大小: 正常 放大

1

主题

3

听众

42

积分

升级  38.95%

该用户从未签到

自我介绍
我是一个数模的喜爱者

群组matlab共享与进阶

群组MATLAB讨论交流群

群组MATLAB

群组Matlab讨论组

跳转到指定楼层
1#
发表于 2010-8-6 22:23 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
%最短路问题(迪克斯特拉算法)
1 {  ?9 w0 ?# b- D! nclear;
. F$ C* n: v. J! X! N: hclc;1 r. u2 q$ i" Y
M=10000;6 N% i+ T: B5 A. d
a(1,:)=[0,50,M,40,25,10];! ^3 B; a. E' ^# z; P. s
a(2,:)=[zeros(1,2),15,20,M,25];
1 E# Z8 Y; @/ k! N( Y+ |a(3,:)=[zeros(1,3),10,20,M];
( c) m7 X1 \$ ^0 j& Ea(4,:)=[zeros(1,4),10,25];# v9 o8 r$ j0 Y7 |) `/ S$ @
a(5,:)=[zeros(1,5),55];
* Q1 W. X, M5 P3 ga(6,:)=zeros(1,6);% x* D1 ?& f9 o/ E) Y- d6 i
a=a+a';' `/ g# @. m2 f) b# H1 T
%length函数返回的是矩阵中行数和列数中较大的长度* H% P9 m) {* r, o: i
pb(1:length(a))=0;%生成一个一行多列的0矩阵: X# l5 ^% ^) f8 ]! [5 A/ _
pb(1)=1; %第一个数赋值为1
0 H  W3 W5 Y- P) {) ]) jindex1=1;$ c, A* P2 D4 k, B$ j: Y0 ^8 ?
index2=ones(1,length(a));%生成一个一行多列的1矩阵
8 P/ g+ W( |$ M- _8 Pd(1:length(a))=M; d(1)=0; temp=1;. Y2 w4 [: I$ q) s* w- V
%sum函数为各行之和, L: c3 _4 H& i* `
while sum(pb)<length(a)
$ x; [3 ~! w) {* J& |/ ]  tb=find(pb==0);%find函数返回的是pb矩阵中数值为0的坐标(2,3,4,5,6....)2 `* Y! W. A2 U1 i9 b2 r" ]/ Q. |
  d(tb)=min(d(tb),d(temp)+a(temp,tb));% K" H) q9 t+ ]0 U( U4 t2 i5 s6 k
  tmpb=find(d(tb)==min(d(tb)));
8 [$ ^! q$ U, S5 F; p1 p! L" }6 K  temp=tb(tmpb(1));
0 M9 w( m5 i7 @# K8 t5 S: s( f8 Y  pb(temp)=1;9 {( S) u  h% k
  index1=[index1,temp];
5 [6 x5 t/ L" B  u7 _3 y, q  index=index1(find(d(index1)==d(temp)-a(temp,index1)));
( {* S  \$ o& `5 Y7 J/ {- {  if length(index)>=2- N# t1 H* p; _
    index=index(1);
( u$ x+ T4 e0 [. B  end9 ~5 q: E+ m3 S: C- @
  index2(temp)=index;' r# d% I1 i. W- l7 a
end# R4 `. ^% M& t& E, H
d,index1,index28 d6 y0 r) Y3 I
迪杰斯特拉算法用于求解一个有向图(也可以是无向图,无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题。算法构思很是巧妙(我这么认为),简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径,再到第二个点的最短路径,直至最后求解完成到第n个点的最短路径,而是求解从原点出发的各有向路径的从小到大的排列(如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了??!!),但是算法最终确实得到了从原点到图中其余各点的最短路径,可以说这是个副产品,对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后,理解算法本身就不是难题了。
( O" O' H4 d$ Q       算法把一个图(G)中的点划分成了若干部分:. s! k: B! w5 M1 b" z9 N7 ^
       1):原点(v);; O2 u% n7 E0 S, `% f/ V8 t
       2):所有周边点(C);% @# x3 j0 h& H7 d  ?7 X: I; ]9 I
       另外有一个辅助集合S,从v到S中的点的最短路径已经求得。S的最初状态是空集。  P7 D" D+ _9 e' ?
       这样就可以进一步划分图(G):
8 |' D: M. M- K       1):原点(v);) v% x, P/ S1 d8 M
       2):已求出v至其最短路径的周边点(S);
6 ^* A3 D5 p- @  ?8 C9 C       3):尚未求出v至其最短路径的周边点(Other=C-S);
8 z8 O$ E( t7 x       算法的主体思想:
# O  _& {/ O6 I( }           A、找到v——Other所有路径中的的最短路径vd=v——d(Other的一个元素);
" H3 k5 |% X( k, y; ]5 S, w! N* v  qB、找到v——S——Other所有路径中的的最短路径vi=v——i(Other的一个元素);
9 V& L) |$ Y8 xC、比较vd和vi如果vd<=vi则将d加入S且从Other中删除,否则将i加入S且从Other中删除。
: C; u$ ~% y2 t' k1 x  M9 e* J重复以上步骤直至Other为空集。/ L) w7 Y9 O5 q& i
4 _+ [, x, S# |: L$ \
我们求得的最短路径是升序排列的,那为什么下一条最短路径就存在于v——
/ X, y7 U7 K) e. \% A
$ b: U: I, ?6 K6 Y+ f: H9 Z
zan
转播转播0 分享淘帖0 分享分享1 收藏收藏0 支持支持1 反对反对0 微信微信
紫辰 实名认证       

12

主题

16

听众

1304

积分

升级  30.4%

  • TA的每日心情
    擦汗
    2013-2-5 09:29
  • 签到天数: 35 天

    [LV.5]常住居民I

    自我介绍
    200 字节以内

    不支持自定义 Discuz! 代码

    群组学术交流A

    群组数学建模保研联盟

    群组Matlab讨论组

    群组湖南大学数学建模

    群组学术交流B

    回复

    使用道具 举报

    linmatsas 实名认证       

    53

    主题

    13

    听众

    3591

    积分

    逍遥游

  • TA的每日心情
    奋斗
    2014-12-2 09:53
  • 签到天数: 54 天

    [LV.5]常住居民I

    自我介绍
    额。。。。世界上最讨厌的事情就是自我介绍。。。

    邮箱绑定达人 新人进步奖 发帖功臣 最具活力勋章

    群组Matlab讨论组

    群组数学建模

    群组小草的客厅

    群组2012数学一考研交流

    群组C 语言讨论组

    回复 紫辰 的帖子7 d' B4 M# ~: A' Y# [& g
    8 `( b. k# t0 I" m0 }

    3 p4 a$ l) v) q  b    我是说好像……人家在贴源程序吧…………
    回复

    使用道具 举报

    wajm_011 实名认证       

    3

    主题

    6

    听众

    1163

    积分

    升级  16.3%

  • TA的每日心情
    郁闷
    2012-2-14 03:19
  • 签到天数: 13 天

    [LV.3]偶尔看看II

    自我介绍
    建模,加油加油!!!

    群组数学建摸协会

    群组哈尔滨工业大学建模团

    群组东北三省联盟

    群组Matlab讨论组

    群组数学建模保研联盟

    回复

    使用道具 举报

    salad6        

    0

    主题

    2

    听众

    30

    积分

    升级  26.32%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    queniao        

    0

    主题

    2

    听众

    30

    积分

    升级  26.32%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    snrl        

    0

    主题

    3

    听众

    69

    积分

    升级  67.37%

    该用户从未签到

    新人进步奖

    楼主,你写得实在是太好了。我惟一能做的,就只有把这个帖子顶上去这件事了
    回复

    使用道具 举报

    chshfxfx        

    0

    主题

    2

    听众

    67

    积分

    升级  65.26%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    icm        

    0

    主题

    2

    听众

    70

    积分

    升级  68.42%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    libin1984        

    0

    主题

    2

    听众

    50

    积分

    升级  47.37%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-11 17:37 , Processed in 1.474800 second(s), 108 queries .

    回顶部