数学建模社区-数学中国

标题: Dijkstra算法及实现（附代码） [打印本页]
作者: shengivp    时间: 2018-2-10 17:23
标题: Dijkstra算法及实现（附代码）
% U$ y1 q, n( H/ B2 E3 _( m
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
& P" ^3 F- e! s' S
  }& {) N# I+ Y9 r8 f4 UDijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
- h5 }* [8 Y6 k# h% |* O) b, D& D) [2 t3 R5 _2 @) J
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
  |& d9 R3 r! Y" z; y
2 W; a6 |- \! X6 ^. j其采用的是贪心法的算法策略
# V- L3 o) T" M" B$ N* C+ b1 [/ `! D4 [0 B/ _' F
大概过程：
; s! ^' z8 `+ {8 x4 h# i& M' I
1 G! Y( l0 A" F5 i创建两个表，OPEN, CLOSE。+ Y, q* g4 C1 ~! ?& D) t% s

0 f& s6 ]$ K$ a& xOPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
* X8 P# a( d% a# `0 M
/ ?5 Q7 E7 ~% O& j1． 访问路网中距离起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
; j9 z0 a, D' y- p- p! x
: j1 [& h4 o& a4 _6 }0 _2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。8 p3 C, _1 [  i! w" h

7 D: o1 R4 U+ D& g" p/ Y4 D* ^3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。% M8 a! k. I1 t3 E: K% A. z

$ y  ?8 Y+ Q' e4． 重复第2和第3步,直到OPEN表为空，或找到目标点。0 c! A9 N1 M8 k5 b# L6 i

! T" S% s. ~  A. ^
源代码见附件！
% Z: ^9 s! O7 r( p7 z2 C% A3 ]
源代码见附件！
  h5 d3 L& I  e) I: B5 w
源代码见附件！
; v# t, w8 M  z7 U

2 i4 q7 o# D$ i% Z$ F4 d! M$ u, o6 M7 L0 ^

, H5 U* Z6 p0 f  `/ P
& f0 ?# x% B: j* s  o; j) Q- i+ u# C5 M, w$ y8 J) W" H) @
7 X2 F: Q% f& y9 F4 h

$ d* m- a9 f5 ^: T

dijk实现代码.txt

7.68 KB, 下载次数: 43, 下载积分: 体力 -2 点
作者: 2388589074    时间: 2018-2-21 12:16
okokokokok
0 Y) l3 G, ^  d
作者: 1283170951    时间: 2018-6-3 11:12
发表回复谢谢休息休息" z: Z5 f9 o% E/ A0 f8 l" j/ J! N
作者: 1359260642    时间: 2021-5-18 08:36
2 D6 a' \. \: u2 A9 ?/ R

5 O  s6 u( T& s" j' `3 X: ?3 Q/ Z6 J3 ^$ I7 G2 Q3 N& K
请问这个使用matlab实现的吗？" m' G: s9 }6 e% ]
作者: 1359260642    时间: 2021-5-18 08:39
如果需要改动是需要改哪里呢，抱歉，因为没有学过这个算法，想学习一下，但是有点看不明白
- k- c. g% c9 t$ ^* u% B



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5