Dijkstra短路径算法.docx

Dijkstra最短路径算法————————————————————————————————作者:————————————————————————————————日期: Dijkstra最短路径算法摘要OSPF是由IETF的IGP工作组为IP网开发的一种能适应大型网络需要的典型的链路状态路由协议,它可以迅速地检测AS内的拓扑变化,经过一个比较短的收敛期后,重新计算出无环路由。在OSPF中采用的是Dijkstra算法来实现最短路径的计算,做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的,可能会有很大的差别,而对于一个大型的网络来讲,选路的效率往往就是网络的生命,算法的重要性不言而喻。关键词OSPF最短路径Dijkstra第1章绪论最短路径算法是计算机科学与地理信息科学等领域研究的热点,其算法有很多种,其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径,并且能够适应网络拓扑的变化,性能稳定,,关于它的求解方法,,是一位名叫EdsgerWybeDijkstra(迪杰斯特拉)的荷兰计算机科学家,他不仅给出了求解的基本思想,,,人们逐渐从两个方面来研究最短路径,,发展出了很多高效的算法,其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1].而不确定情况下对最短问题的研究又分成了四个方面:研究路段长度随机变化的最短路径问题,以Frank和Mirchandani为代表;研究不同费用函数最短路径问题,以Loui、Muethy和Sarkar为代表;研究时间独立情况下的路段长度随机变化的最短路径问题,Hall、LiPingFu、、Elise和Hani为代表;研究路段长度为区间范围的最短路径问题,,第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”.,基于网络的权矩阵,需要根据其节点与距离之间的关系,形成关联矩阵、邻接矩阵与距离矩阵,需要定义的数组来存储数据,其中为网络的节点数,当网络的节点数较大时,、,在搜索过程中和最短路径节点相连通的节点为临时标记节点,每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点,,,,,但由于它遍历计算的节点很多,,(迪杰斯特拉)算法是典型的单源最短路径算法,,,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,,:未标记结点、,在搜索过程中和最短路径中的结点相连通的结点为临时标记结点,每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点,直至找到目标结点或者所