We show how to maintain a shortest, path tree of a general directed graph G with unit edge weights and n vertices, during a sequence of edge deletions or a sequence of edge insertions, in O(n) amortized time per operation using linear space. Distance queries can be answered in time linear in the length of the retrieved path. These results are extended to the case of integer edge weights in [1,C], with a bound of O(C~n) amortized tiem per operation. We also show how to maintain a breadth-first search tree of a directed graph G in an incremental or a decremental setting in O(n) amortized time per operation using linear space.
展开▼
