Loading...
Please wait, while we are loading the content...
Similar Documents
Shortest Path Trees Computation in Dynamic Graphs (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Chan, Edward P. F. Yang, Yaya |
| Abstract | Let G =(V,E,w) be a simple digraph, in which all edge weights are non-negative real numbers. Let G ′ be obtained from G by the application of a set of edge weight updates to G. Lets∈V, and let Ts and T ′ s be a Shortest Path Tree (SPT) rooted at s in G and G ′ , respectively. The Dynamic Shortest Path (DSP) problem is to compute T ′ s from Ts. For the DSP problem, we correct and extend a few existing SPT algorithms to handle multiple edge weight updates. We prove that these extended algorithms are correct. The complexity of these algorithms is also analyzed. To evaluate the proposed algorithms, we compare them with the well-known static Dijkstra algorithm. Extensive experiments are conducted with both real-life and artificial data sets. The real-life data are road system graphs obtained from the Connecticut road system and are relatively sparse. The artificial data are randomly generated graphs and are relatively dense. The experimental results suggest the most appropriate algorithms to be used under different circumstances. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dynamic Graph Shortest Path Tree Computation Edge Weight Well-known Static Dijkstra Algorithm Simple Digraph Real-life Data Artificial Data Set Road System Graph Spt Algorithm Artificial Data Different Circumstance Connecticut Road System Non-negative Real Number Multiple Edge Weight Update Appropriate Algorithm Shortest Path Tree Extensive Experiment Dynamic Shortest Path Dsp Problem |
| Content Type | Text |
