新Dijkstra最短路径算法.docx

Dijkstra最短路径算法
西安科技大学 通信学院
1
Dijkstra最短路径算法
西安科技大学 通信学院
2
摘 要
OSPF 是由 IE算法，使用其可以求得图中一点到其他各顶点的最短路径．原始的Dijkstra算法将网络结点分成3局部：未标记结点、临时标记结点和永久标记结点．网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法．
假设每个点都有一对标号〔,〕，其中是从起源点到点的最短路径的长度〔从顶点到其本身的最短路径是零路〔没有弧的路〕，其长度等于零〕； 那么是从到的最短路径中点的前一点．求解从起源点到点的最短路径算法的根本过程如下：
〔1〕初始化．起源点设置为：①,为空；②所有其他点:,；③标记起源点，记,其他所有点设为未标记的．
〔2〕检验从所有已标记的点到其直接连接的未标记的点j的距离，并设置：式中，是从点到的直接连接距离．
〔3〕选取下一个点．从所有未标记的结点中，选取中最小的一个：
，〔所有未标记的点〕，点就被选为最短路径中的一点，并设为已标记的．
〔4〕找到点的前一点．从已标记的点中找到直接连接到点的点，作为前一点，设置：=．
西安科技大学 通信学院
6
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
西安科技大学 通信学院
8
4
4
0
10
50
30
60
表2-1 0节点到4节点的最短路径
Dijkstra算法的优缺点
Dijkstra算法能够保证100%找到最优解，但其搜索速度较慢，搜索效率非常低，时间花费较多，一般只能用于离线的路径规划问题．
如节点数为的图，用Dijkstra算法计算最短路径总共需要迭代次，每次迭代都新加一个节点到临时节点集合中，由于第i次迭代时不在临时节点集合中的节点数为．即第次迭代需对个节点进行处理，因此其所需的处理数为：
对n个节点网络的时间复杂度是．在实际应用当中，使用Dijkstra算法查找最短路径时消耗大量的时间进行数据的比拟，本文对Dijkstra算法进行分析，通过改变算法实现减少不必要节点计算的时间，提高算法的效率到达对其进行优化．
第3章 基于Dijkstra算法的优化算法的研究
几种优化算法
减小算法中成功搜索的搜索范围
减小算法中成功搜索的搜索范围以尽快到达目标节点．在对现实问题中的交通图初始化为网络拓扑图时，虽然终点，而源点尚未确定，但依据常识离案发地段最近的派出所应为案发地段所在辖区派出所，或其周边派出所，也就是源点的选取范围可以确定．