Experimental Study of Dynamic Single-Source Shortest Path Algorithm

Qian Cai Xiao; Ming Qi Li; Wen Qiang Guo

doi:10.4028/www.scientific.net/AMM.58-60.1493

Paper Titles

Improved GM (1, 1) Model in the Economic Growth Forecast of Qinghai
p.1471

A Novel XML-Based Power Resource Modeling Framework for Power System Heterogeneous Data Integrating
p.1476

Stress Concentration Factor for some DTK Joints Based on Finite Element
p.1482

Fast Intra Prediction Algorithm for H.264 High Profile Based on Image Texture
p.1487

Experimental Study of Dynamic Single-Source Shortest Path Algorithm
p.1493

An Adaptive Genetic Algorithm Based on Multi-Population Parallel Evolutionary for Highway Alignment Optimization Model
p.1499

Fault Detection of WSN Based on Spatial Correlation
p.1504

Modeling on Washing Machine Mode and Water-Saving Improvement
p.1511

Analogical Basis Decomposition for Randomized Sampling Signal Reconstruction
p.1517

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 58-60Experimental Study of Dynamic Single-Source...

Experimental Study of Dynamic Single-Source Shortest Path Algorithm

Abstract:

In this paper, software Inet 3.0 is applied to generate topology, which randomly generates dynamic topology nodes. Based on dynamic shortest path algorithms put forward by P.Narvaez, Xiaobin et al, we analyzed the time efficiency of dynamic and static shortest path algorithms, the different time efficiency inner dynamic shortest path algorithms, and the relationship of time efficiency between topology and dynamic shortest path algorithms. The result shows that Xiaobin algorithm is statistically better than Narvaez algorithm about 20-30 percent. Dynamic algorithms are not always better than static algorithms considering the amount of changed topology. Dynamic and static algorithms are roughly same when the amount of changed topology holds 10 percent. Dynamic algorithms perform better when less than 10 percent, otherwise static algorithms will be better. The time efficiency of dynamic algorithms is related to special topology.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 58-60)

Pages:

1493-1498

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.58-60.1493

Citation:

Cite this paper

Online since:

June 2011

Authors:

Qian Cai Xiao, Ming Qi Li, Wen Qiang Guo

Keywords:

Dynamic Shortest Path Algorithm, Shortest Path Algorithm, SPT

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] E. Dijkstra: A Note Two Problems in Connection with Graphs. Numerical Math., 1(1959), pp.269-271.

Google Scholar

[2] Reinhard Bauer and Dorother Wagner Batch: Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study. LNCS 5526 (2009), pp.51-62.

DOI: 10.1007/978-3-642-02011-7_7

Google Scholar

[3] P. Narvaez, K.Y. Siu and H.Y. Tzeng: New Dynamic Algorithms for Shortest Path Tree Computation. IEEE/ACM Transactions on Networking, Vol. 8 (2000), pp.734-746.

DOI: 10.1109/90.893870

Google Scholar

[4] P. Narvaez, K.Y. Siu and H.Y. Tzeng: New Dynamic SPT Algorithm Based on a Ball-and-String Model. IEEE/ACM Transactions on Networking, Vol. 9 (2001), pp.706-718.

DOI: 10.1109/90.974525

Google Scholar

[5] Xiao. B, Cao.J. N and Qin.L.: Dynamic SPT Update for Multiple Link State Decrements in Networking Routing. Supercomput, 46(2008), pp.237-256.

DOI: 10.1007/s11227-007-0164-y

Google Scholar

[6] Xiao. B, Cao.J. N, Shao.Z. L and Edwin H. -M. Sha: An Efficient Algorithm for Dynamic Shortest Path Tree Update in Network Routing. Communications And Networks, Vol. 9(2007), pp.499-510.

DOI: 10.1109/jcn.2007.6182886

Google Scholar