Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

November Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the November 2021 Edition of the journal. The last date of research paper submission is October 15, 2021.

An Efficient Technique for Computing Shortest Path Tree in Dynamic Graphs

Neeraj Kumar Maurya, R. R. Sedamkar Published in Algorithms

International Journal of Applied Information Systems
Year of Publication: 2014
© 2013 by IJAIS Journal
10.5120/ijais14-451133
Download full text
  1. Neeraj Kumar Maurya and R R Sedamkar. Article: An Efficient Technique for Computing Shortest Path Tree in Dynamic Graphs. International Journal of Applied Information Systems 7(1):42-48, April 2014. BibTeX

    @article{key:article,
    	author = "Neeraj Kumar Maurya and R. R. Sedamkar",
    	title = "Article: An Efficient Technique for Computing Shortest Path Tree in Dynamic Graphs",
    	journal = "International Journal of Applied Information Systems",
    	year = 2014,
    	volume = 7,
    	number = 1,
    	pages = "42-48",
    	month = "April",
    	note = "Published by Foundation of Computer Science, New York, USA"
    }
    

Abstract

This paper proposes an efficient technique for computing shortest path in dynamic graph. Which finds shortest path in a given graph which is static or intended to change its weight frequently. If that graph is static i. e. not changing its weight then SPT is being calculated once and that remains same. If graph is dynamic i. e. changing its weight then this technique finds new SPT with traversing minimum number of nodes or vertices. This technique extends a few state-of-the-art dynamic SPT algorithms to handle multiple edge weight updates, and find the SPT. A function based on the location of current node/ state is used to vary the cost of the goal node and the search is done with minimum the state space and exploring only affected nodes, by using these approaches problem is solved in minimum time. Based on experimental results on sample data set we propose to device an algorithm which efficiently handles different traffic conditions. The performance of this algorithm is measured on the basis of Graph size, number of changed edge (NCE). To evaluate the proposed dynamic algorithm, comparison is done with the well-known static Dijkstra algorithm. Where proposed algorithm's complexity is O(bd) in worst case O(E) in average case and O(1) in best case.

Reference

  1. D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni, "Fully Dynamic Algorithms for Maintaining Shortest Paths Trees," J. Algorithms, vol. 34, no. 2, pp. 251-281, 2000.
  2. D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasquale, "Experimental Analysis of Dynamic Algorithms for the Single-Source Shortest- Path Problem," ACM J. Experimental Algorithms, vol. 3, p. 5, 1998.
  3. P. Narva´ez, K. Siu, and H. Tzeng, "New Dynamic Algorithms for Shortest Path Tree Computation," ACM Trans. Networking, vol. 8, no. 6, pp. 734-746, 2000.
  4. P. Narva´ez, K. Siu, and H. Tzeng, "New Dynamic SPT Algorithm Based on a Ball-and-String Model," ACM Trans. Networking, vol. 9, no. 6, pp. 706-718, 2001.
  5. Edward P. F. Chan and Yaya Yang,"Shortest Path Tree Computation in Dynamic Graph,"IEEE Transaction On Computers, vol 58. No. 4. , April 2009.
  6. G. Ramalingam and T. W. Reps, "An Incremental Algorithm for a Generalization of the Shortest-Path Problem," J. Algorithms, vol. 21, no. 2, pp. 267-305, 1996. [7 ] E. W. Dijkstra, "A Note on Two Problems in Connection with Graphs," Numerical Math. , vol. 1, pp. 269-271, 1959.
  7. B. Xiao, Q. Zhuge, and E. H. -M. Sha, "Efficient Algorithms forDynamic Update of Shortest Path Tree in Networking," J. Computers and Their Applications, vol. 11, no. 1, 2003.
  8. G. Ramalingam and T. W. Reps, "On the Computational Complexity of Dynamic Graph Problems," Theoretical Computer Science, vol. 158, nos. 1-2, pp. 233-277, 1996.
  9. G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, and U. Nanni,"Incremental Algorithms for Minimal Length Paths," J. Algorithms,vol. 12, no. 4, pp. 615-638, 1991.

Keywords

Dynamic Dijkstra, Dynamic Graph, Graph, Directed Graph.