A Method for Maintaining Shortest Paths in Dynamic Networks
Yuanzhi Wang · 2007
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.