首 页 | 兆通产品部 | 兆通工程部 | 兆通维护部 | 兆通销售站 | 天猫店铺 | 技术中心 | 方案中心 | 典型案例 | 兆通论坛
当前页面:首页>>OSPF算法详细说明 2
[2009-9-25]
 

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

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

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

  下面我们开始展开递归构造最短路径树的过程:

  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

  V0V450

  10

  45V0Null在初始状态,最短路径树中只有节点V0,候选路径就是V0直接相连的边代表的路径。

  V0V1

  V0V4

  V0V2V350

  45

  35V0、V2V0V0

  V0V2

  V0V2在所有候选路径中最短,所以放入最短路径树,V2放入集合A。考察所有以刚放入集合A的节点V2为起点的边的终点,对其中不在集合A中的节点,这里只有节点V3,计算从V0出发经节点V2,到达V3的路径V0V2V3的值,因为候选路径中没有到V3的路径,所以V0V2V3路径直接放入候选路径集合。

  V0V1

  V0V4

  V0V2V3V1

  V0V2V3V450

  45

  45

  55V0、V2、V3V0V0

  V0V2

  V0V2V3

  V0V2V3在所有候选路径中最短,所以放入最短路径树,V3放入集合A。考察所有以刚放入集合A的节点V3为起点的边的终点,对其中不在集合A中的节点,这里是节点V1,V4,计算从V0出发经节点V3,到达这两个节点的路径V0V2V3V1和V0V2V3V4的路径值,并和候选路径中已有的到达V1、V4的路径值进行比较:V0V2V3V1小于V0V1,所以V0V1从候选路径中删除,V0V2V3V1放入候选路径集合;V0V2V3V4比V0V4大,所以V0V4在候选路径中保留,V0V2V3V4路径废弃不用。


[返回列表]

首页 | 网络工程 | 综合布线 | 安防监控 摄像头 摄像机 | 方案中心 | 技术中心 | TOP | 典型案例
电话:025-83693855
Copyright © 2005-2006 All Rights Reserved
南京总部: 南京市珠江路成贤大厦7楼