Dijkstra最短路径算法样稿.docx

Dijkstra最短路径算法
摘 要
OSPF 是由 IETF IGP 工作组为 IP 网开发一个能适应大型网络需要经典 链路状态路由协议，它能够快速地检测 AS 内拓扑改变，经过一个比较短收敛期 后，重新计算出无环路由。在 OSPF 中采取是 Dijkstra 算法来实现最短路径计算， 做到了选路高效、可靠。不一样算法在时间上开销是不一样，可能会有很大 差异，而对于一个大型网络来讲，选路效率往往就是网络生命，算法重 要性不言而喻。
关键词 OSPF 最短路径 Dijkstra
第1章 绪论
最短路径算法是计算机科学和地理信息科学等领域研究热点，其算法有很多个，其中传统Dijkstra算法通常见于计算一个源节点到全部其它节点最小代价路径，而且能够适应网络拓扑改变，性能稳定，所以能够在运输路线计划等领域全部应用广泛．
中国外最短路径算法发展及其概况
最短路径在20世纪初开始受到大家重视，相关它求解方法，当初有很多科学家在研究．但给出求解基础思想人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra（迪杰斯特拉）荷兰计算机科学家，她不仅给出了求解基础思想，还给出了算法．她给出算法关键处理问题是从某一个固定点到其它各点最短路径问题．以后这个算法被誉为一代经典，被称作Dijkstra算法．以后，大家逐步从两个方面来研究最短路径，分为完全信息情况下和不确定情况下．确定情况下对最短路径研究过程中，发展出了很多高效算法，其中1958年Bellman算法、1959年Dijkstra算法、1969年Dreyfus算法已成为确定情况下经典算法[1]．而不确定情况下对最短问题研究又分成了四个方面：研究路段长度随机改变最短路径问题，以Frank和Mirchandani为代表；研究不一样费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下路段长度随机改变最短路径问题，Hall、LiPing Fu、、Elise和Hani为代表；研究路段长度为区间范围最短路径问题，以Tomas和Rajeev为代表．其中，第二方面问题研究得出结论是“当目标是期望最短路径时问题转化为将边权重用期望值表示最短路径问题”
．
传统Dijkstra算法仍然存在部分问题
原始Dijkstra算法在存放图形数据和运算时，基于网络权矩阵，需要依据其节点和距离之间关系，形成关联矩阵、邻接矩阵和距离矩阵，需要定义数组来存放数据，其中为网络节点数，当网络节点数较大时，将占用大量计算机内存．
原始Dijkstra算法在运行时通常将网络节点分为未标识节点、临时标识节点和永久标识节点3种类型．网络中全部节点首先初始化为未标识节点，在搜索过程中和最短路径节点相连通节点为临时标识节点，每一次循环全部是从临时标识节点中搜索距离原点路径长度最短节点作为永久标识节点，直至找到目标节点或全部节点全部成为永久标识节点才结束算法．依据算法描述可知对临时标识节点遍历成为Dijkstra算法瓶颈，影响了算法实施效率．
第2章 Dijkstra经典算法
引言
Dijkstra算法是经典最短路算法，用于计算一个节点到其它全部节点最短路径．关键特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法能得出最短路径最优解，但因为它遍历计算节点很多，所以效率低．怎样改善这一经典算法，成为了实现图论中赋权图中处理实际问题关键课题．
原理及应用
Dijkstra(迪杰斯特拉)算法是经典单源最短路径算法，用于计算一个节点到其它全部节点最短路径．关键特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法是很有代表性最短路径算法，在很多专业课程中全部作为基础内容有具体介绍，如数据结构，图论，运筹学等等．Dijkstra通常表述通常有两种方法，一个用永久和临时标号方法，一个是用OPEN, CLOSE表方法，这里均采取永久和临时标号方法．该算法要求图中不存在负权边．
原理
Dijkstra算法是1959年由E．W．Dijkstra提出图论中求最短路径一个著名算法，使用其能够求得图中一点到其它各顶点最短路径．原始Dijkstra算法将网络结点分成3部分：未标识结点、临时标识结点和永久标识结点．网络中全部结点首先初始化为未标识结点，在搜索过程中和最短路径中结点相连通结点为临时标识结点，每次循环全部是从临时标识结点中搜索距源点路径长度最短结点作为永久标识结点，直至找到目标结点或全部结点全部成为永久标识结点来结束算法．
假设每