Semidynamic algorithms for maintaining single-source shortest path trees

We consider the problem of updating a single-source shortest path tree in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log rr) amortized time per vertex update: where a vertex is considered updated ii it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O(root mlog n) amortized time perverter update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6]. require simple datastructures that are really suitable for a practical and straightforward implementation.