Call for Paper - May 2015 Edition
IJCA solicits original research papers for the May 2015 Edition. Last date of manuscript submission is April 20, 2015. Read More
Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 107 - Number 16
Year of Publication: 2014
|
10.5120/18837-0372 |
Akanksha Singh and Pramod Kumar Mishra. Article: Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm. International Journal of Computer Applications 107(16):23-27, December 2014. Full text available. BibTeX
@article{key:article,
author = {Akanksha Singh and Pramod Kumar Mishra},
title = {Article: Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {107},
number = {16},
pages = {23-27},
month = {December},
note = {Full text available}
}
Abstract
In this paper, we have examined the comparative study of Floyd Warshall algorithm and the Rectangular algorithm. We have tested these two algorithms on random graphs generated by the Erdös – Renyi (ER) model. The evaluation of the algorithms for different probabilities show that the Floyd Warshall algorithm gives slightly better performance for dense graphs while the Rectangular algorithm works better for sparse graphs.
References
- R. Bellman. : On a routing problem, Quarterly Journal of Applied Mathematics 16 (1958) 87-90.
- E. W. Dijkstra. : A note on two problems in connexion with graphs". Numerische Mathematik 1 (1959) 269-271.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 3rd Ed. New York, MIT Press and McGraw Hill.
- R. W. Floyd. : Algorithm 97 Shortest path, Communications of the ACM 5 (1962) 345.
- G. Gallo and S. Pallottino: Shortest paths algorithms, Annals of Operation Research 12(1988) 3-79.
- B. V. Cherkassky, Andrew V. Goldberg, Tomas Radzik. : Shortest paths algorithms: Theory and experimental evaluation, Mathematical Programming 73 (1996) 129-74.
- S. Pettie. : A new approach to all-pairs shortest paths on real-weighted graph, Theoretical Computer Science 312 (2004) 47-74.
- S. Hougardy: The Floyd-Warshall algorithm on graphs with negative cycles, Information Processing Letters 110 (2010) 279-281.
- S. Peyer, D. Rautenbach and J. Vygen. : A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing, Journal of Discrete Algorithms 7 (2009) 377-390.
- Deng, Y. Chen, Y. Zhang and S. Mahadevan. : Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Applied Soft Computing 12 (2012) 1231-1237.
- J. B. Orlin, K. Madduri, K. Subramani, and M. Williamson. : A faster algorithm for the single source shortest path problem with few distinct positive lengths, Journal of Discrete Algorithms 8 (2010) 189-198.
- Y. Han and T. Takaoka. : An O(n3loglog n/log2n) Time Algorithm for All Pairs Shortest Paths.
- W. Peng, X. Hu, F. Zhao, J. Su. : A Fast algorithm to find all-pairs shortest paths in complex networks, Procedia Computer Science 9 (2012) 557-566.
- S. Warshall. : A theorem on boolean matrices, Journal of the ACM 9 (1962) 11-12.
- A. Aini and A. Salehipour: Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem, Applied Mathematical letters 25 (2012) 1-5.
- P. Erdös and A. Renyi: On the evolution of Random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960) 17-61.