基于可变权值的动态最短路径算法∗

摘要

有向网络中，最短路径的计算在交通、通信等实际问题中有着重要的应用。通过对现有动态最短路径算法的深入研究，提出一种处理网络拓扑变化的全动态最短路径算法（Increase or Decrease of Edge Weight for Shortest Path Tree，IDEWSPT）。该算法利用初始最短路径树（Shortest Path Tree SPT）的信息，建立一个SPT的更新队列，当网络拓扑发生变化时，将更新范围局限在受拓扑变化影响的节点中，从而达到控制冗余更新的目的。算法复杂度分析和仿真结果显示，IDEWSPT算法具更高的时间效率。%The shortest path problem of directed network is significant in the transportation and communi-cation systems. Based on the research on the present dynamic SPT algorithm, we proposed a new complete dynamic SPT algorithm for the network topology changing. This algorithm establishes an SPT update queue and pays attention only to the changes of nodes and edges by taking use of the useful information provided by the existing SPT, which can reduce redundant update. The complexity analysis of algorithm and simulation results shows that IDEWSPT has higher efficiency.