文档介绍：--------------------------校验:_____________-----------------------日期:_____________Dijkstra最短路径算法Dijkstra最短路径算法摘要OSPF是由IETF的IGP工作组为IP网开发的一种能适应大型网络需要的典型的链路状态路由协议,它可以迅速地检测AS内的拓扑变化,经过一个比较短的收敛期后,重新计算出无环路由。在OSPF中采用的是Dijkstra算法来实现最短路径的计算,做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的,可能会有很大的差别,而对于一个大型的网络来讲,选路的效率往往就是网络的生命,算法的重要性不言而喻。关键词OSPF最短路径Dijkstra第1章绪论最短路径算法是计算机科学与地理信息科学等领域研究的热点,其算法有很多种,其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径,并且能够适应网络拓扑的变化,性能稳定,,关于它的求解方法,,是一位名叫EdsgerWybeDijkstra(迪杰斯特拉)的荷兰计算机科学家,他不仅给出了求解的基本思想,,,人们逐渐从两个方面来研究最短路径,,发展出了很多高效的算法,其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1].原始Dijkstra算法在存储图形数据和运算时,基于网络的权矩阵,需要根据其节点与距离之间的关系,形成关联矩阵、邻接矩阵与距离矩阵,需要定义的数组来存储数据,其中为网络的节点数,当网络的节点数较大时,、,在搜索过程中和最短路径节点相连通的节点为临时标记节点,每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点,,,,,但由于它遍历计算的节点很多,,(迪杰斯特拉)算法是典型的单源最短路径算法,,,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,,:未标记结点、,在搜索过程中和最短路径中的结点相连通的结点为临时标记结点,每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点,(,),其中是从起源点到点的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);:(1):①,为空;②所有其他点:,;③标记起源点,记,其他所有点设为未标记的.(2)检验从所有已标记的点到其直接连接的未标记的点j的距离,并设置:式中,是从点到的直接连接距离.(3),选取中最小的一个:,(所有未标记的点),点就被选为最短路径中的一点,并设为已标记的.(4)