数学建模社区-数学中国

标题: Dijkstra算法及实现(附代码) [打印本页]

作者: shengivp    时间: 2018-2-10 17:23
标题: Dijkstra算法及实现(附代码)

0 P% P6 }3 _$ U  B3 wDijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。
+ y( L) K" @% _$ |, X' H* i
1 C- ]2 O3 `# PDijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
7 t. W1 U) Y) ]5 e3 ^  Z; ^' F0 d0 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 W3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到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" O4 @' 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

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