数学建模社区-数学中国
标题:
Dijkstra最短路径算法演示
[打印本页]
作者:
蒙萌
时间:
2009-8-26 22:23
标题:
Dijkstra最短路径算法演示
算法介绍：
/ x2 J7 U8 a( [6 @1 i
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
& r# y7 z+ e' p3 O
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
; `' G8 `+ [- s! b2 V/ X
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
|- l6 I i8 X
dj=min［dj, dk+lkj］
6 J! P/ w# C+ D& P
式中，lkj是从点k到j的直接连接距离。
# w9 Q9 I( g9 F8 R: r
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
) ^) D" w& Q1 e- n, ?% l
di=min［dj, 所有未标记的点j］
1 A! A, c! K- b# n
点i就被选为最短路径中的一点，并设为已标记的。
1 ^4 p8 R( n& d# E5 m* N
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
! u2 w+ k& @ A
i=j*
! m) k7 g; n( {( K, b0 U
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续
作者:
蒙萌
时间:
2009-8-26 22:24
希望大家指证
作者:
alazyrabbit
时间:
2009-8-26 22:47
可以使用Find-Union Set，更简单！
作者:
troops123
时间:
2010-7-13 19:33
太好啦，，哈哈哈哈哈
作者:
troops123
时间:
2010-7-13 19:33
太好啦 哈哈哈哈哈
作者:
troops123
时间:
2010-7-13 19:35
太好啦 哈哈哈哈哈
作者:
troops123
时间:
2010-7-13 19:45
太好啦 哈哈哈哈哈
作者:
troops123
时间:
2010-7-13 19:51
太好啦 哈哈哈哈哈
作者:
alair009
时间:
2012-1-26 11:04
支持一,下楼主辛苦了
11904353806607842189515399431061318562933323172351902062712511545587355567747319
作者:
婷婷玉立
时间:
2012-1-29 20:29
可以看看运筹学
作者:
婷婷玉立
时间:
2012-1-29 20:30
或者是模糊数学，
作者:
婷婷玉立
时间:
2012-1-29 20:30
对童靴应该有帮助
作者:
婷婷玉立
时间:
2012-1-29 20:31
赞同，╭(╯3╰)╮
作者:
婷婷玉立
时间:
2012-1-29 20:31
呦呦呦呦╭(╯3╰)╮
作者:
婷婷玉立
时间:
2012-1-29 20:31
作者:
婷婷玉立
时间:
2012-1-29 20:32
作者:
婷婷玉立
时间:
2012-1-29 20:32
作者:
婷婷玉立
时间:
2012-1-29 20:32
作者:
婷婷玉立
时间:
2012-1-29 20:33
作者:
scutyf
时间:
2012-2-4 13:55
婷婷玉立 发表于 2012-1-29 20:29
% P$ X# |8 A6 b, O
可以看看运筹学
8 G8 A7 {3 ]+ ]0 l
运筹学里面有这个内容？？？？？哪个版本的运筹啊
作者:
Asgard
时间:
2012-2-4 14:22
这东西不需要吧
作者:
a6070933
时间:
2012-2-4 22:16
先谢楼主了
作者:
wssl103050
时间:
2012-5-31 11:37
呵呵 分享一下挺好的额
作者:
刘伶广场
时间:
2013-5-3 19:59
作者:
我是男神
时间:
2015-7-29 09:59
taihaola hahahahhahahahahah
( b8 {- Y4 r8 a& C
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
太好啦 哈哈哈哈哈
