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

Abstract: 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.

Key words: shortest path tree, algorithm, dynamic updating, extended shortest path tree