Shortest Path Tree Computation in Dynamic Graphs

摘要

Let G = (V, E, w) be a simple digraph, in which all edge weights are nonnegative real numbers. Let G^{prime} be obtained from G by an application of a set of edge weight updates to G. Let sin V and let T_{s} and T_{s}^{prime} be Shortest Path Trees (SPTs) rooted at s in G and G^{prime}, respectively. The Dynamic Shortest Path (DSP) problem is to compute T_{s}^{prime} from T_{s}. Existing work on this problem focuses on either a single edge weight change or multiple edge weight changes in which some of them are incorrect or are not optimized. We correct and extend a few state-of-the-art dynamic SPT algorithms to handle multiple edge weight updates. We prove that these algorithms are correct. Dynamic algorithms may not outperform static algorithms all the time. To evaluate the proposed dynamic algorithms, we compare them with the well-known static Dijkstra algorithm. Extensive experiments are conducted with both real-life and artificial data sets. The experimental results suggest the most appropriate algorithms to be used under different circumstances.