数学建模社区-数学中国
标题:
Dijkstra最短路径算法演示
[打印本页]
作者:
蒙萌
时间:
2009-8-26 22:23
标题:
Dijkstra最短路径算法演示
算法介绍：
& O7 K% G# F0 q# |7 z
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
+ t. Y. e" ?' `. ]8 J
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
8 r; w0 K; s2 s" _* T R8 X
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
) u2 s o/ S' c
dj=min［dj, dk+lkj］
0 Z R3 w* }# q; q* F. {
式中，lkj是从点k到j的直接连接距离。
, T% n1 s* Z9 P" |% ~
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
; y/ t) r# ]6 a+ y+ b: r
di=min［dj, 所有未标记的点j］
6 j9 N7 E+ C2 ^9 `( S
点i就被选为最短路径中的一点，并设为已标记的。
& ^( @, s5 u$ ?* x4 `5 D: X m
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
+ i t+ ~2 I/ b/ z# _
i=j*
- O1 Z; ?. g J9 X3 h. ~' n
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
3 a& V6 Z$ W% ] Y3 ?7 p3 A/ N
可以看看运筹学
; Z; j( A. r @$ b1 p5 _
运筹学里面有这个内容？？？？？哪个版本的运筹啊
作者:
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
( n, T& V0 i8 c2 V/ h( D1 G
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
太好啦 哈哈哈哈哈
