The week's pick
Random Articles
Reseach Article
An Improved Algorithm for Finding All Pair Shortest Path
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 47 - Number 25 |
| Year of Publication: 2012 |
| Authors: Himanshu Garg, Paramjeet Rawat |
10.5120/7539-0492
|
Himanshu Garg, Paramjeet Rawat . An Improved Algorithm for Finding All Pair Shortest Path. International Journal of Computer Applications. 47, 25 ( June 2012), 35-37. DOI=10.5120/7539-0492
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.
Index Terms
Keywords