Call for Paper - March 2023 Edition
IJCA solicits original research papers for the March 2023 Edition. Last date of manuscript submission is February 20, 2023. Read More

An Improved Algorithm for Finding All Pair Shortest Path

Print
PDF
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 47 - Number 25
Year of Publication: 2012
Authors:
Himanshu Garg
Paramjeet Rawat
10.5120/7539-0492

Himanshu Garg and Paramjeet Rawat. Article: An Improved Algorithm for Finding All Pair Shortest Path. International Journal of Computer Applications 47(25):35-37, June 2012. Full text available. BibTeX

@article{key:article,
	author = {Himanshu Garg and Paramjeet Rawat},
	title = {Article: An Improved Algorithm for Finding All Pair Shortest Path},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {47},
	number = {25},
	pages = {35-37},
	month = {June},
	note = {Full text available}
}

Abstract

Floyd Warshall's Algorithm is a simple and widely used algorithm to compute shortest path between all pairs of vertices in an edge weighted directed graph. It can also be used to detect the presence of negative cycles. Many researchers have given many other approaches for finding all pair shortest path but they reduced the complexity by using complex data structures. In this paper, we suggests a technique for finding shortest path based on Floyd Warshall's algorithm with reduced time complexity and also by not using complex data structures. We present an O(n ) time algorithm for finding all pair shortest paths. Our proposed algorithm is an improvement on the previous algorithm whose best result was O(n )

References

  • P K Singh, Rajendra Kumar Member, IACSIT and Vijay Shankar Pandey,"An Efficient Algorithm for All Pair Shortest Paths", International Journal of Computer and Electrical Engineering, Vol. 2, No. 6, December, 2010
  • Stefan Hougardy , "The Floyd-Warshall Algorithm on Graphs with Negative Cycles ",Information Processing Letters 110 (2010), 279-281
  • Udaya Kumar Reddy K. R, and K. Viswanathan Iyer, "All-pairs shortest-paths problem for unweighted graphs in O(n log n) time", International Journal of Computational and Mathematical Sciences 3:5 2009
  • Yijie Han, "An O(n log log n/ log n) time algorithm for all pairs shortest paths", Manuscript, 2009.
  • Wikipedia. Floyd-Warshall algorithm — Wikipedia, The Free Encyclope-dia, 2009. [Online; accessed 20-November-2009].
  • Gary J. Katz1,2 and Joseph T. Kider Jr1 , "All-Pairs Shortest-Paths for Large Graphs on the GPU",Graphics Hardware (2008) David Luebke and John D. Owens (Editors)
  • Timothy M. Chan, "All-pairs shortest paths with real weights in O(n / log n) Time", Algorithmica, 50:236–243, 2008.
  • Yijie Han," An O(n (log log n/ log n) ) time algorithm for all pairs shortest paths", Algorithmica, 51:428–434, 2008.
  • Yijie Han, "A note of an O(n / log n) time algorithm for all pairs shortest paths", Information Processing Letters, 105:114–116, 2008.
  • Timothy M. Chan, "More algorithms for all-pairs shortest paths in weighted Graphs", In STOC07, pages 590–598, 2007.
  • Uri Zwick, "A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths", Algorithmica, 46:181–192, 2006.
  • Tadao Takaoka, "An O(n log log n/ log n) time algorithm for the all-pairs shortest path problem", Information Processing Letters, 96:155–161, 2005.
  • Seth Pettie, "A new approach to all-pairs shortest paths on real-weighted Graphs", Theoretical Computer Science, 312:47–74, 2004.
  • Tadao Takaoka, "A new upper bound on the complexity of the all pairs shortest path problem", Information Processing Letters, 43:195–199, 1992.
  • Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, "Introduction To Algorithms" MIT. Press, Mcgraw-Hill Book Company, ISBN 0-262-03141-8, 1990.
  • Michael L. Fredman, "New bounds on the complexity of the shortest path Problem" ,SIAM Journal on Computing, 5(1):83–89, 1976.
  • Tadao Takaoka, "A faster algorithm for the all-pairs shortest path problem and its application" In K. -Y. Chwa and J. I. Munro, Springer-Verlag LNCS Vol 3106, pp 278–289.