快捷通道

QQ登录

只需要一步，快速开始

  注册地址  找回密码

数学建模社区-数学中国

留学>>
123下一页
返回列表 发新帖
查看: 9389|回复: 24
打印 上一主题 下一主题

Dijkstra最短路径算法演示

[复制链接]
字体大小: 正常 放大
蒙萌 实名认证       

4

主题

4

听众

76

积分

升级  74.74%

该用户从未签到

新人进步奖

跳转到指定楼层
1#
发表于 2009-8-26 22:23 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
算法介绍：
* z' {# h- l& \) d* [4 HDijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：1 d" v: u1 g3 f. t2 s# B
　　1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。$ \) g% V6 @8 w! t5 n+ X. i
　　2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：5 ?3 _5 W$ j- E2 S
dj=min［dj, dk+lkj］& x  W3 k. r1 a" G/ c
式中，lkj是从点k到j的直接连接距离。
7 B! w4 e& t1 H$ C! V4 e9 P　　3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：* Q; S- `6 y6 \1 m+ j( j
di=min［dj, 所有未标记的点j］9 I9 x) m" m: {; f, t" ~6 Y  k
点i就被选为最短路径中的一点，并设为已标记的。
, Q* H' `. ?4 a/ x9 T0 E& Y　　4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
1 y: G; T& g: V$ L" Ei=j*
3 e% P/ c. [, I5 n. T5 F　　5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持2 反对反对0 微信微信
回复

使用道具 举报

蒙萌 实名认证       

4

主题

4

听众

76

积分

升级  74.74%

该用户从未签到

新人进步奖

2#
发表于 2009-8-26 22:24 |只看该作者 |招呼Ta 关注Ta
希望大家指证
回复

使用道具 举报

alazyrabbit        

3

主题

4

听众

59

积分

升级  56.84%

该用户从未签到
3#
发表于 2009-8-26 22:47 |只看该作者 |招呼Ta 关注Ta
可以使用Find-Union Set，更简单！
回复

使用道具 举报

troops123 实名认证       

5

主题

2

听众

373

积分

升级  24.33%

  • TA的每日心情
    开心
    2014-7-25 18:31

    • 签到天数: 58 天

    [LV.5]常住居民I

    自我介绍
    我是一个很喜欢数学建模的大学本科生，，我为数模疯狂

    群组: B题讨论群
    4#
    发表于 2010-7-13 19:33 |只看该作者 |招呼Ta 关注Ta
    太好啦，，哈哈哈哈哈
    回复

    使用道具 举报

    troops123 实名认证       

    5

    主题

    2

    听众

    373

    积分

    升级  24.33%

  • TA的每日心情
    开心
    2014-7-25 18:31

    • 签到天数: 58 天

    [LV.5]常住居民I

    自我介绍
    我是一个很喜欢数学建模的大学本科生，，我为数模疯狂

    群组: B题讨论群
    5#
    发表于 2010-7-13 19:33 |只看该作者 |招呼Ta 关注Ta
    太好啦  哈哈哈哈哈
    回复

    使用道具 举报

    troops123 实名认证       

    5

    主题

    2

    听众

    373

    积分

    升级  24.33%

  • TA的每日心情
    开心
    2014-7-25 18:31

    • 签到天数: 58 天

    [LV.5]常住居民I

    自我介绍
    我是一个很喜欢数学建模的大学本科生，，我为数模疯狂

    群组: B题讨论群
    6#
    发表于 2010-7-13 19:35 |只看该作者 |招呼Ta 关注Ta
    太好啦  哈哈哈哈哈
    回复

    使用道具 举报

    troops123 实名认证       

    5

    主题

    2

    听众

    373

    积分

    升级  24.33%

  • TA的每日心情
    开心
    2014-7-25 18:31

    • 签到天数: 58 天

    [LV.5]常住居民I

    自我介绍
    我是一个很喜欢数学建模的大学本科生，，我为数模疯狂

    群组: B题讨论群
    7#
    发表于 2010-7-13 19:45 |只看该作者 |招呼Ta 关注Ta
    太好啦  哈哈哈哈哈
    回复

    使用道具 举报

    troops123 实名认证       

    5

    主题

    2

    听众

    373

    积分

    升级  24.33%

  • TA的每日心情
    开心
    2014-7-25 18:31

    • 签到天数: 58 天

    [LV.5]常住居民I

    自我介绍
    我是一个很喜欢数学建模的大学本科生，，我为数模疯狂

    群组: B题讨论群
    8#
    发表于 2010-7-13 19:51 |只看该作者 |招呼Ta 关注Ta
    太好啦  哈哈哈哈哈
    回复

    使用道具 举报

    alair009        
    头像被屏蔽

    0

    主题

    4

    听众

    361

    积分

    升级  20.33%

  • TA的每日心情
    郁闷
    2012-2-3 19:26

    • 签到天数: 5 天

    [LV.2]偶尔看看I
    9#
    发表于 2012-1-26 11:04 |只看该作者 |招呼Ta 关注Ta
    提示: 作者被禁止或删除 内容自动屏蔽
    回复

    使用道具 举报

    婷婷玉立        

    1

    主题

    4

    听众

    361

    积分

    升级  20.33%

  • TA的每日心情
    慵懒
    2013-5-7 09:24

    • 签到天数: 21 天

    [LV.4]偶尔看看III
    10#
    发表于 2012-1-29 20:29 |只看该作者 |招呼Ta 关注Ta
    可以看看运筹学
    回复

    使用道具 举报

    123下一页
    返回列表 发新帖
    高级模式
    B Color Image Link Quote Code Smilies
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩

    • 电话咨询

    • 04714969085

    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2025-5-10 06:49 , Processed in 0.797580 second(s), 98 queries .

    回顶部