OSPF 中的最短路径算法 内部公开 2005-05-12 华为三康机密，未经许可不得扩散 第 1 页, 共 9 页 OSPF中的最短路径算法 测试中心 陈旭盛 现实生活中的网络拓扑，可以抽象成由节点（路由器）和边（路由器之间的链路）构成的有向连通图，链路的代价可以抽象成边的权函数。之所以称图为有向图，是因为同一条链路（边）不同方向的权值可能不一样。 我们知道，对于有向连通图，以任意一个节点为起点，利用最短路径算法可以计算出到其他节点的最短路径。那么，对于能抽象成有向连通图的网络拓扑来说，也可以利用最短路径算法先计算出以任意一台路由器为起点，到达其他路由器的最短路径，然后根据各路由器的网络连接情况可以得到到各个网络的路由路径。 OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样，都是相当经典的最短路径算法。本文将对Dijkstra算法进行系统的描述，并给出一个简洁的证明。 1 Dijkstra 算法介绍 在数学上，以某个节点为起点，计算到其他节点的最短路径的算法，称为“单源最短路径” 算法。求“单源最短路径”的问题在数学上可以精确描述如下： “单源最短路径” 问题：已知一个有n个节点(V0..n)构成的有向连通图G＝（V，E），以及图中边的权函数C (E)，其中V代表节点集合，E表示所有边的集合，并假设所有权非负，求由G中指定节点V0到其他各个节点的最短路径。 Dijkstra算法是很经典的求解上述问题的算法，其基本想法是设计一种最短路径树的构造方法，按非降次序逐条构造从V0到各个节点的最短路径，第一步找到和V0相距最短的节点以及到这个节点的路径，第二步找到和V0相距次短的节点以及到这个节点的路径，如此反复，最后找到V0到所有节点的最短路径，构造出整棵最短路径树。 对上述构造方法的一个直观考虑是：和V0相距最短的节点应该在和V0直接相邻的节点中，和V0相距次短的节点要么在和V0直接相邻的节点中，要么在和这些相邻节点相邻的节点中，如此逐步扩散考虑，应该就可以找到和V0相距最短、次短、…….第n短的节点以及对应的路径，而且因为是连通图，最后肯定所有节点都能全部考虑到，也就能完成整棵最短路 OSPF 中的最短路径算法 内部公开 2005-05-12 华为三康机密，未经许可不得扩散 第 2 页, 共 9 页 径树的构造。 事实上，上述直观考虑是对的，Dijkstra算法是对上述过程的一个提炼和优化：和V0相距最短的节点是和V0直接相连的节点没错；相距次短的节点范围可以缩小为，和V0...
