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

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