OSPF中的最短路径算法

    现实生活中的网络拓扑，可以抽象成由节点（路由器）和边（路由器之间的链路）构成的有向连通图，链路的代价可以抽象成边的权函数。之所以称图为有向图，是因为同一条链路（边）不同方向的权值可能不一样。

    我们知道，对于有向连通图，以任意一个节点为起点，利用最短路径算法可以计算出到其他节点的最短路径。那么，对于能抽象成有向连通图的网络拓扑来说，也可以利用最短路径算法先计算出以任意一台路由器为起点，到达其他路由器的最短路径，然后根据各路由器的网络连接情况可以得到到各个网络的路由路径。

    OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样，都是相当经典的最短路径算法。本文将对Dijkstra算法及OSPF协议对Dijkstra算法的使用进行介绍。

    1Dijkstra算法介绍

    在数学上，以某个节点为起点，计算到其他节点的最短路径的算法，称为“单源最短路径” 算法。求“单源最短路径”的问题在数学上可以精确描述如下：

    “单源最短路径” 问题：已知一个有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：剩余的其他节点的集合。

    对于路径，我们分成三个集合：

    （1）已经选入最短路径树的路径的集合

    （2）候选路径集合：下一条加入最短路径树的路径将从这个集合中选入

    （3）剩余的其他路径的集合（被废弃的路径或者还未考虑的路径）

    为了更好的理解，有必要对这里的路径定义进行一下强调：路径是指以V0为起点，其他节点为终点的由一条或多条边组成的一个有序集。边，可以理解为路径中的一段，只有到和V0直接相邻的节点的路径才直接对应一条边。从V0到所有节点，都可能存在一条或多条路径，非最短路径在计算过程中将会被废弃，放入集合III。

    从前面的描述中可以明显看出，Dijkstra算法是一个递归构造过程，因为任何递归都必须有明确的初始状态，所以我们有必要先得到上述Dijkstra算法中定义的集合的初始值：

    l以V0为起点计算最短路径的话，初始状态时显然有且只有V0在集合A中，所以集合A的初始值为V0。集合B的初始值为剩余节点。

    l 前面提到过，下一个加入集合A的节点，一定是和V0直接有边相连的节点，因此，加入最短路径树的第一条路径也必然在这些和V0直接相连的边所代表的路径中产生，所以集合II的初始值就是和V0直接相连的边构成的路径。另外，初始状态最短路径树为空，所以集合I的初始值为空。集合I、II明确了的话，集合III自然明确。

[1] [2] [3] [4] 下一页