- 在线时间
- 1 小时
- 最后登录
- 2018-2-23
- 注册时间
- 2012-7-12
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 4 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 5
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 7
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 1
升级 0% 该用户从未签到
- 自我介绍
- 爱好数学建模,参与建模竞赛
|
( i9 P" E4 O* b
Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。# v- e: k* t; k, h* Q, Q1 r/ \
* C5 r) W8 Y8 x9 D$ ^6 \
Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。
1 t0 C' `, c9 v0 `" G: S) C' k/ f, a# _+ B' f$ u2 Q. _1 J
Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式,Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致,这里均采用OPEN,CLOSE表的方式。. K8 c: U8 J1 @8 f B2 k: f8 ` i
; K: L M1 E7 `
其采用的是贪心法的算法策略
: C0 n$ p5 y/ ~+ A2 z' C0 B7 I6 ~" N" h1 V3 u/ C; ~
大概过程:) T6 h: m4 u* K2 Z* q' R5 b6 O$ s: y
7 L7 t7 f" T9 }/ K* L! ]- n
创建两个表,OPEN, CLOSE。' ^) D! g- N8 Q7 d4 V# b
9 o( j& y+ }0 G. E% N! |OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。: Y# n' a2 h6 h4 d+ q1 ?2 D/ j, _& D
9 _: c* O8 o% V* m) F; W2 R/ G
1. 访问路网中距离起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。3 f+ A0 l0 N9 y! x2 }/ G
- u( J4 N2 N4 l4 u9 I V2. 从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。' {0 w* E2 i( C4 A
/ p3 N/ G+ P5 B3. 遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。
7 o* v; ?3 ]' ^9 q! k, p1 U
8 p _/ d- v( H! t- @) ^: u/ Z: }4. 重复第2和第3步,直到OPEN表为空,或找到目标点。
- B3 _: ]$ E6 _1 z+ _- n
5 P; W4 T# T$ |) v. g$ a源代码见附件!
2 @( b) m6 u! B4 _$ S! a$ E源代码见附件!
& s$ W5 b# I* v8 I* F9 l源代码见附件!
6 a6 r: V* u Z0 W& I# ?2 o$ i
3 I% M! _) v( t; L' b8 V `, h( v7 D' x! o# t& m
% \% v/ U) H9 {0 R& x
: m# ]2 W& e0 |6 V7 F2 r
9 x; F$ L$ ^$ m# H8 n/ G
5 H( [& c6 E l4 O
3 R) c6 F% X' O+ L |
zan
|