Algorithms for dynamic allpairs shortest path problem 


Authors 
 Krivoshein D. Y. 
 Marchenko A.M. 
Date of publication 
 2012 

Abstract 
 In this paper we consider the problem of recalculation shortest paths after changing the weight of any single edge. We can observe two different cases: increasing and decreasing of the weight. For the first problem we propose the algorithm, which time complexity depends on graph structure and Dijkstra's algorithm time complexity for a given graph, and in most cases the time complexity is better that FloydWarshall. In case of decreasing the weight the algorithm which requires O(n^2) time is described. 
Keywords 
 dynamic graph, shortest path problem, changing the weight of an edge, incremental algorithm 
Library reference 
 Krivoshein D. Y., Marchenko A.M. Algorithms for dynamic allpairs shortest path problem // Problems of Perspective Micro and Nanoelectronic Systems Development  2012. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2012. P. 263266. 
URL of paper 
 http://www.mesconference.ru/data/year2012/pdf/D171.pdf 