数学建模社区-数学中国
标题:
Dijkstra算法及实现（附代码）
[打印本页]
作者:
shengivp
时间:
2018-2-10 17:23
标题:
Dijkstra算法及实现（附代码）
0 P% P6 }3 _$ U B3 w
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
+ y( L) K" @% _$ |, X' H* i
1 C- ]2 O3 `# P
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
7 t. W1 U) Y) ]5 e3 ^ Z; ^' F0 d
0 E7 `/ Z7 p3 P1 u2 A. M/ K/ Q$ e; P
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
+ S0 c! l' d+ E
: r/ |" g) r2 d: T3 U7 {9 {9 l
其采用的是贪心法的算法策略
, c) b1 ~' A! M: F5 p: N
+ F) Y& }7 b0 \" g9 c& q
大概过程：
3 {0 ]% _+ P1 f; x9 U! [
3 Y* a/ A' T' Y- p- h' U
创建两个表，OPEN, CLOSE。
5 w- ~: c0 R- |/ d
I$ v1 }; x: K' t
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
# M8 B7 O4 z5 D% B {
% |/ H* {# ^) [
1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
" M7 b& x R! H W5 F
8 V L( A/ O- k3 Q; ^
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
: N& z, F; l; L
8 q1 ?; T) W. p. @0 H3 W
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
) U9 [/ p" C' X2 s" {. v& ~7 x
' X; V* m" M% F' u1 J& o5 D3 i% W
4． 重复第2和第3步,直到OPEN表为空，或找到目标点。
$ C. y( p: A* A0 Y# L. Z& `
7 J6 i$ ]- R- u* ]0 \+ X
源代码见附件！
# v1 Y& d a* f- u8 o9 P
源代码见附件！
3 V5 P, |1 A/ H& g
源代码见附件！
7 a* t! s% ?5 `3 Y1 `9 d9 b
" f* y- a- ^1 m. s- E
! ?. P6 X5 g5 y" O
4 @' Y' z! ?' \9 w2 J
) G& p' K7 U3 |% |4 m9 G
$ G8 w& ]3 \" m3 p
3 ^' I5 ~6 q$ U* M' S$ M! F# P6 w2 ~
# Y% O0 Y# ?4 G( E/ X/ k
dijk实现代码.txt
2018-2-10 17:22 上传
点击文件名下载附件
下载积分: 体力 -2 点
7.68 KB, 下载次数: 43, 下载积分: 体力 -2 点
作者:
2388589074
时间:
2018-2-21 12:16
okokokokok
7 ~! U: f4 r* _8 y
作者:
1283170951
时间:
2018-6-3 11:12
发表回复谢谢休息休息
. C' ?$ V7 P: @
作者:
1359260642
时间:
2021-5-18 08:36
5 x% T7 d0 f1 R/ c
* B+ E) W1 D2 S# Y2 u; W: ^
% K, z9 Y! u1 l9 K
请问这个使用matlab实现的吗？
. f. R# ~7 ~, j( V: h0 Y" U* G
作者:
1359260642
时间:
2021-5-18 08:39
如果需要改动是需要改哪里呢，抱歉，因为没有学过这个算法，想学习一下，但是有点看不明白
: ^; N' q7 R, U/ _
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
