下载此文档

OSPF中的最短路径算法.doc


文档分类:IT计算机 | 页数:约8页 举报非法文档有奖
1/8
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/8 下载此文档
文档列表 文档介绍
OSPF中的最短路径算法测试中心陈旭盛现实生活中的网络拓扑,可以抽象成由节点(路由器)和边(路由器之间的链路)构成的有向连通图,链路的代价可以抽象成边的权函数。之所以称图为有向图,是因为同一条链路(边)不同方向的权值可能不一样。我们知道,对于有向连通图,以任意一个节点为起点,利用最短路径算法可以计算出到其他节点的最短路径。那么,对于能抽象成有向连通图的网络拓扑来说,也可以利用最短路径算法先计算出以任意一台路由器为起点,到达其他路由器的最短路径,然后根据各路由器的网络连接情况可以得到到各个网络的路由路径。OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样,都是相当经典的最短路径算法。本文将对Dijkstra算法进行系统的描述,并给出一个简洁的证明。Dijkstra算法介绍在数学上,以某个节点为起点,计算到其他节点的最短路径的算法,称为“单源最短路径”算法。求“单源最短路径”的问题在数学上可以精确描述如下:“单源最短路径”问题:已知一个有n个节点(V0..n)构成的有向连通图G=(V,E),以及图中边的权函数C(E),其中V代表节点集合,E表示所有边的集合,并假设所有权非负,求由G中指定节点V0到其他各个节点的最短路径。Dijkstra算法是很经典的求解上述问题的算法,其基本想法是设计一种最短路径树的构造方法,按非降次序逐条构造从V0到各个节点的最短路径,第一步找到和V0相距最短的节点以及到这个节点的路径,第二步找到和V0相距次短的节点以及到这个节点的路径,如此反复,最后找到V0到所有节点的最短路径,构造出整棵最短路径树。对上述构造方法的一个直观考虑是:和V0相距最短的节点应该在和V0直接相邻的节点中,和V0相距次短的节点要么在和V0直接相邻的节点中,要么在和这些相邻节点相邻的节点中,如此逐步扩散考虑,应该就可以找到和V0相距最短、次短、…….第n短的节点以及对应的路径,而且因为是连通图,最后肯定所有节点都能全部考虑到,也就能完成整棵最短路径树的构造。事实上,上述直观考虑是对的,Dijkstra算法是对上述过程的一个提炼和优化:和V0相距最短的节点是和V0直接相连的节点没错;相距次短的节点范围可以缩小为,和V0直接相邻的节点,加上跟刚选中的最短节点直接相邻的节点;相距第三短的节点的范围可以类推得到,即在上一步考察的节点的基础上,加上和次短节点直接相邻的节点。如此逐步构造,可以按非降次序找到到所有节点的最短路径。为了从数学上精确描述上述构造过程,引入了集合的概念对节点和路径进行分类。我们把节点分成两个集合:A:已经选入最短路径树的节点的集合。B:剩余的其他节点的集合。对于路径,我们分成三个集合:I:已经选入最短路径树的路径的集合II:候选路径集合:下一条加入最短路径树的路径将从这个集合中选入。III:剩余的其他路径的集合(被废弃的路径或者还未考虑的路径)。为了更好的理解,有必要对这里的路径定义进行一下强调:路径是指以V0为起点,其他节点为终点的由一条或多条边组成的一个有序集。边,可以理解为路径中的一段,只有到和V0直接相邻的节点的路径才直接对应一条边。从V0到所有节点,都可能存在一条或多条路径,非最短路径在计算过程中将会被废弃,放入集合III。从前面的描述中可以明显看出,Dijkstra算法是一个递归构造过程,因为任何递归都必须有明确的初

OSPF中的最短路径算法 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数8
  • 收藏数0 收藏
  • 顶次数0
  • 上传人wz_198613
  • 文件大小66 KB
  • 时间2019-03-14