Fully dynamic algorithms for maintaining shortest paths trees

We propose fully dynamic algorithms for maintaining the distances and the s hortest paths from a single source in either a directed or an undirected gr aph with positive real edge weights, handling insertions, deletions, and we ight updates of edges. The algorithms require linear space and optimal quer y time. The cost of the update operations depends on the class of the consi dered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance fro m the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the updat e procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded ar boricity, bounded degree, bounded treewidth, and bounded pagenumber. For ge neral graphs with n vertices and m edges the algorithms require O(root m lo g n) worst case time per output update. We also show that, if insertions an d deletions of edges are allowed, then similar amortized bounds hold. (C) 2 000 Academic Press.