数学建模社区-数学中国
标题:
Dijkstra最短路径算法演示
[打印本页]
作者:
蒙萌
时间:
2009-8-26 22:23
标题:
Dijkstra最短路径算法演示
算法介绍：
; o6 N4 E* A" m1 ^
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
( H3 u1 @: u- g7 r; V
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
7 I$ a7 C! k* L1 @: T
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
$ x9 U& V6 _9 A! T; j- n
dj=min［dj, dk+lkj］
3 E/ R- ^: a$ }1 T
式中，lkj是从点k到j的直接连接距离。
( m i0 S$ Z, X( \: e
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
. O7 I) I, V Q) R- P
di=min［dj, 所有未标记的点j］
& H; l. e' L: t
点i就被选为最短路径中的一点，并设为已标记的。
, }+ c5 g4 k4 I
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
$ y( v* ~# H, y0 F* F7 r& i
i=j*
- l% i. m( E/ [6 q3 s
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
; r- y4 [) Z% E) |3 q. C: L
可以看看运筹学
2 j" @) P/ R( b# Z5 ~7 I
运筹学里面有这个内容？？？？？哪个版本的运筹啊
作者:
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
9 d$ \. s* O2 R7 ?1 h( B& A
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
; r- y4 [) Z% E) |3 q. C: L
太好啦 哈哈哈哈哈
