CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm

by Akanksha Singh, Pramod Kumar Mishra
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 107 - Number 16
Year of Publication: 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 },
issue_date = { December 2014 },
volume = { 107 },
number = { 16 },
month = { December },
year = { 2014 },
issn = { 0975-8887 },
pages = { 23-27 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume107/number16/18837-0372/ },
doi = { 10.5120/18837-0372 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:41:14.793564+05:30
%A Akanksha Singh
%A Pramod Kumar Mishra
%T Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 107
%N 16
%P 23-27
%D 2014
%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
  1. R. Bellman. : On a routing problem, Quarterly Journal of Applied Mathematics 16 (1958) 87-90.
  2. E. W. Dijkstra. : A note on two problems in connexion with graphs". Numerische Mathematik 1 (1959) 269-271.
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein: Introduction to Algorithms, 3rd Ed. New York, MIT Press and McGraw Hill.
  4. R. W. Floyd. : Algorithm 97 Shortest path, Communications of the ACM 5 (1962) 345.
  5. G. Gallo and S. Pallottino: Shortest paths algorithms, Annals of Operation Research 12(1988) 3-79.
  6. B. V. Cherkassky, Andrew V. Goldberg, Tomas Radzik. : Shortest paths algorithms: Theory and experimental evaluation, Mathematical Programming 73 (1996) 129-74.
  7. S. Pettie. : A new approach to all-pairs shortest paths on real-weighted graph, Theoretical Computer Science 312 (2004) 47-74.
  8. S. Hougardy: The Floyd-Warshall algorithm on graphs with negative cycles, Information Processing Letters 110 (2010) 279-281.
  9. 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.
  10. 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.
  11. 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.
  12. Y. Han and T. Takaoka. : An O(n3loglog n/log2n) Time Algorithm for All Pairs Shortest Paths.
  13. 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.
  14. S. Warshall. : A theorem on boolean matrices, Journal of the ACM 9 (1962) 11-12.
  15. A. Aini and A. Salehipour: Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem, Applied Mathematical letters 25 (2012) 1-5.
  16. 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

Computer Science
Information Sciences

Keywords

Bellman ford algorithm Dijkstra's algorithm Floyd warshall algorithm all pair shortest path algorithm the rectangular algorithm comparison of algorithms.

Powered by PhDFocusTM