Incremental maintenance of all-pairs shortest paths in relational DBMSs

Computing shortest paths is a classical graph theory problem and a central task in many applications. Although many algorithms to solve this problem have been proposed over the years, they are designed to work in the main memory and/or with static graphs, which limits their applicability to many current applications where graphs are highly dynamic, that is, subject to frequent updates. In this paper, we propose novel efficient incremental algorithms for maintaining all-pairs shortest paths and distances in dynamic graphs. We experimentally evaluate our approach on several real-world datasets, showing that it significantly outperforms current algorithms designed for the same problem.