Fully dynamic output bounded single source shortest path problem

Abstract

We consider the problem of maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions and cost updates of edges. We propose fully dynamic algorithms with optimal space requirements and query time. The cost of update operations depends on the class of the considered graph and on the number of vertices that, due to an edge modification, either change their distance from the source or change their parent in the shortest path tree. In the case of graphs with bounded genus (including planar graphs), bounded degree graphs, bounded treewidth graphs and β-near-planar graphs with bounded β, the update procedures require O(log n) amortized time per vertex update, while for general graphs with n vertices and m edges they require O(√ m log n) amortized time per vertex update. The solution is based on a dynamization of Dijkstra's algorithm [6] and requires simple data structures that are suitable for a practical and straightforward implementation.