dijkstra最短路径算法

《dijkstra最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、西安科技大学通信学院Dijkstra最短路径算法11西安科技大学通信学院摘要OSPF是由IETF的IGP工作组为IP网开发的一种能适应大型网络需要的典型的链路状态路由协议，它可以迅速地检测AS内的拓扑变化，经过一个比较短的收敛期后，重新计算出无环路由。在OSPF中采用的是Dijkstra算法来实现最短路径的计算，做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的，可能会有很大的差别，而对于一个大型的网络来讲，选路的效率往往就是网络的生命，算法的重要性不言而喻。关键词OSPF最短路径Dijkstra1

2、1西安科技大学通信学院第1章绪论最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛．1.1国内外最短路径算法的发展及其概况最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究．但给出求解的基本思想的人直到1959年才出现，是一位名叫EdsgerWybeDijkstra（迪杰斯特拉）的荷兰计算机科学家，他

3、不仅给出了求解的基本思想，还给出了算法．他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题．后来这个算法被誉为一代经典，被称作Dijkstra算法．后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下．确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1]．而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径

4、问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPingFu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表．其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”．11西安科技大学通信学院1.2传统Dijkstra算法仍然存在的一些问题原

5、始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义的数组来存储数据，其中为网络的节点数，当网络的节点数较大时，将占用大量的计算机内存．原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型．网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所

6、有节点都成为永久标记节点才结束算法．根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率．第2章Dijkstra经典算法2.1引言Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径．主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低．如何改进这一经典算法，成为了实现图论中赋权图中解决实际问题的重要课题．2.2原理及应用Dijkstra(迪杰斯特拉)算法是

7、典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径．主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等．Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,11西安科技大学通信学院CLOSE表的方式，这里均采用永久和临时标号的方式．该算法要求图中不存在负权边．2.2.1原理Dijkstra算法是1959年由E．W．Dijkstra提出

8、的图论中求最短路径的一个著名的算法，使用其可以求得图中一点到其他各顶点的最短路径．原始的Dijkstra算法将网络结点分成3部分：未标记结点、临时标记结点和永久标记结点．网络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有的结点都成为永久标记结点来结束算法．假设每个点都有一