Dijkstra最短路径算法.docx

Dijkstra最短路径算法
西安科技大学 通信学院
1
Dijkstra最短路径算法
西安科技大学 通信学院
1
第1章 绪论
如下：
（1）初始化．起源点设置为：①,为空；②所有其他点:,；③标记起源点，记,其他所有点设为未标记的．
（2）检验从所有已标记的点到其直接连接的未标记的点j的距离，并设置：式中，是从点到的直接连接距离．
（3）选取下一个点．从所有未标记的结点中，选取中最小的一个：
，（所有未标记的点），点就被选为最短路径中的一点，并设为已标记的．
（4）找到点的前一点．从已标记的点中找到直接连接到点的点，作为前一点，设置：=．
西安科技大学 通信学院
3
0
（5）标记点．如果所有点已标记，则算法完全推出，否则，记=，转到（2）再继续．
100

10

4
1

30

10
50 60
3
2
20


图2-1 Dijkstra算法最短路径应用演示图
循环
红点集
初始化
-
0
10
30
100
1
1
0
10
60
30
100
2
3
0
10
50
30
90
3
2
0
10
50
30
60
西安科技大学 通信学院
4
4
4
0
10
50
30
60
表2-1 0节点到4节点的最短路径
Dijkstra算法的优缺点
Dijkstra算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题．
如节点数为的图，用Dijkstra算法计算最短路径总共需要迭代次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为．即第次迭代需对个节点进行处理，因此其所需的处理数为：
对n个节点网络的时间复杂度是．在实际应用当中，使用Dijkstra算法查找最短路径时耗费大量的时间进行数据的比较，本文对Dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率达到对其进行优化．
第3章 基于Dijkstra算法的优化算法的研究
几种优化算法
减小算法中成功搜索的搜索范围
减小算法中成功搜索的搜索范围以尽快到达目标节点．在对现实问题中的交通图初始化为网络拓扑图时，虽然终点已知，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定．利用MapObjects2组件提供的
西安科技大学 通信学院
5
（expression）记录集筛选方法，根据案发地段（终点）的不同，动态选取案发地段所在辖区及相邻辖区的道路图层及派出所图层数据进行最短路径查询，从而有效地减少了拓扑图中节点总数的值．
改进算法的存储结构
在实际工作中，还要建立起空间数据结构．网络数据结构使用的是“边和节点”的数据结构，该数据结构是建立在图论的基础上，节点可用来定义边的连接关系．对于网络数据的存储，传统的是采用图论中的邻接矩阵方法，其存储量为(为网络中节点数)