一种维持动态网络中最短路径的方法

本论文提出解决动态网络中多源-目的点对最短路径路动态问题的有效方案。针对动态网络中的边权被改变后,需要扫描所有的边重新计算所有点对之间最短路径,我们提出采用相应的数据结构,使每次边权改变后,只需重新计算含该边的源-目的点对间最短路径,即最低限度的扫描动态图中的边,提高维持所有点对之间最短路径算法的时间性能。

A Method for Maintaining Shortest Paths in Dynamic Networks

This paper presents a new solution to the dynamic all-pairs shortest paths problem. It is need to recalculate all-pair shortest paths after each edge-weight update for the existing algorithm. It can recalculate the affected shortest paths after each edge-weight update for method in this paper by presenting corresponding data structure and the method. Indeed the method attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph. It's superiority in terms of the average number of processed nodes,scanned edges when compared with the existing algorithms.