一种不需记录后继的扩展SPT动态更新算法

摘要：

动态SPT算法是在图的拓扑改变时,以原有SPT为基础作局部更新;SPT动态更新需要解决寻找因为该改变而需要修正最短路径的相关节点的问题.对于传统的SPT定义先扩展,使节点记录距离相等的一条或多条最短路径,称之为ESPT.提出了一种不需记录后继的ESPT动态更新算法并加以证明,通过证明还说明在ESPT定义下该算法找到的所有节点都是动态更新所必要且充分的.给出算例,列出操作过程,对不同复杂度的图进行计算实验,将其结果与经典静态算法进行了对比.

关键词：最短路径树、算法、动态更新、扩展最短路径树

所属期刊栏目：47

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：71-73,136