OSPF算法详细说明
下面我们开始展开递归构造最短路径树的过程：
l 第一步：从集合II中选择一条最短的路径，放入最短路径树，相应的，这条路径的终点对应的节点（这里记为X）应该从集合B移入集合A。
l 第二步：考察所有从X出发的边的终点，考虑其中不属于集合A的节点，这里记为Y，计算从V0出发经X到达Y的路径值，计算方法为：最短路径树中V0到节点X的路径值加上（X，Y）这条边的值。为了描述方便，我们把从V0出发经X到达Y的路径记为（V0X）Y。接着考察集合II中的候选路径，如果其中没有到节点Y的路径，则直接把路径(V0X)Y作为候选路径加入集合II；如果集合II中已经有到节点Y的路径，则进行比较，如果这条路径值小于或等于路径 (V0X)Y的路径值，那么路径(V0X)Y作为被废弃的路径放入集合III，否则原集合II中到Y的路径被废弃放入集合II，（V0X）Y作为候选路径放入集合II。对于Y节点有多个的情况，按第二步的方法一个一个的计算和比较。
l 重复第一步和第二步，直到集合II和集合B为空。
第二步事实上是对候选路径的一个重新计算过程，因为在集合A中引入了新的节点后，考察的范围变大了，很可能在原来节点范围内认为到某个节点的最短路径已经不再是最短路径了，这时候，需要根据第二步的方法进行调整。
为了让大家更好的理解这一构造过程，这里举一个较为典型的例子，如下是一个有向图：
计算这个有向连通图的最短路径树的过程如下： 候选路径集合 路径长度 最短路径树中的节点(集合A) 最短路径树 说明 V0V1 V0V2 V0V4 50 10 45 V0 Null 在初始状态，最短路径树中只有节点V0，候选路径就是V0直接相连的边代表的路径。 V0V1 V0V4
天下网吧·网吧天下
闽公网安备35010202000238号