Research Article
Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 107 - Issue 16 |
| Published: December 2014 |
| Authors: Akanksha Singh, Pramod Kumar Mishra |
10.5120/18837-0372
|
Akanksha Singh, Pramod Kumar Mishra . Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm. International Journal of Computer Applications. 107, 16 (December 2014), 23-27. DOI=10.5120/18837-0372
@article{ 10.5120/18837-0372,
author = { Akanksha Singh,Pramod Kumar Mishra },
title = { Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm },
journal = { International Journal of Computer Applications },
year = { 2014 },
volume = { 107 },
number = { 16 },
pages = { 23-27 },
doi = { 10.5120/18837-0372 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Akanksha Singh
%A Pramod Kumar Mishra
%T Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm%T
%J International Journal of Computer Applications
%V 107
%N 16
%P 23-27
%R 10.5120/18837-0372
%I Foundation of Computer Science (FCS), NY, USA
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.
Index Terms
Keywords