Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

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

Copyright © 2009-2019 IPPM RAS. All Rights Reserved.

Design of site: IPPM RAS