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

Novel algorithm for non-descendents-memorizing extended SPT dynamic updating

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

Dynamic SPT（Shortest Paths Tree） algorithms,through local updating based on original SPT,have to find out which nodes need updating their shortest paths due to the topology change of the graph.A novel data structure defined by ESPT which extends the traditional SPT can record one or more equidistant paths in each node.A new dynamic algorithm for ESPT＇s updating is proposed with an example and its solution process as well as the certification,with which can also be pointed out that under the ESPT structure the nodes grabbed by this algorithm are all exactly the ones which need updating.Computation experiments are conducted for some graphs of different complexity,whose results are shown compared with those of the static algorithm.