| Algorithms for dynamic all-pairs 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 Floyd-Warshall. 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 all-pairs shortest path problem // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2012. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2012. P. 263-266. |
| URL of paper |
| | http://www.mes-conference.ru/data/year2012/pdf/D171.pdf |
