Dijkstra最短路径算法.docx

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