Dynamically Maintaining Shortest Path Trees under Batches of Updates

"In this paper we focus on dynamic batch algorithms for single source shortest paths in graphs with positive real edge weights. A dynamic algorithm is called batch if it is able to handle graph changes that consist of multiple edge updates at a time, i.e. a batch. We propose a new algorithm to process a decremental batch (containing only delete and weight increase operations), a new algorithm to process an incremental batch (containing only insert and weight decrease operations), and a combination of these algorithms to process arbitrary sequences of incremental and decremental batches. These algorithms are update-sensitive, namely they are efficient w.r.t. to the number of nodes in the shortest paths tree that change the parent and\/or the distance from the source as a consequence of the changes."