Research Article
Algorithms of All Pair Shortest Path Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 120 - Issue 15 |
| Published: June 2015 |
| Authors: Susmita |
10.5120/21300-3876
|
Susmita . Algorithms of All Pair Shortest Path Problem. International Journal of Computer Applications. 120, 15 (June 2015), 1-6. DOI=10.5120/21300-3876
@article{ 10.5120/21300-3876,
author = { Susmita },
title = { Algorithms of All Pair Shortest Path Problem },
journal = { International Journal of Computer Applications },
year = { 2015 },
volume = { 120 },
number = { 15 },
pages = { 1-6 },
doi = { 10.5120/21300-3876 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A Susmita
%T Algorithms of All Pair Shortest Path Problem%T
%J International Journal of Computer Applications
%V 120
%N 15
%P 1-6
%R 10.5120/21300-3876
%I Foundation of Computer Science (FCS), NY, USA
Abstract
This paper is based on survey of various algorithms for all pair shortest path problem (APSP) on arbitrary real weighted directed graphs. This paper has summarized existing methods for solving shortest-path problems. In particular, we have addressed both sequential and parallel algorithms. We begin with a review of conventional sequential shortest-path algorithms and later, we have discussed blocked and vectorized implementation, thereby with the aim of reducing computational effort.
References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press, Sep. 2001.
- http://en. wikipedia. org/wiki/Floyd%E2%80%93Warshall_algorithm
- R. Iris Bahar,Gary D. Hachtel,Enrico Macii,Abelardo Pardo,Massimo Poncino,Fabio Somenzi, "An ADD Based Algorithm for Shortest Path Back-Tracing of Large Graphs",1066-1395/94, 1994,pages-248-251,IEEE
- R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel,E. Macii, A. Pardo, F. Somenzi, "Algebraic Decision Diagrams and their Applications", ICCAD-93: ACM/IEEE 1993 International Conference on Computer Aided Design, Santa Clara, CA, November 1993.
- Hiroki Yanagisawa," A Multi-Source Label-Correcting Algorithm for the All-Pairs Shortest Paths Problem", RT0882,sept 2009.
- B. V. Cherkassky, A. V. Goldberg, and T. Radzik, "Shortest paths algorithms: theory and experimental evaluation", Mathematical Programming, Vol. 73, Issue 2, pp. 129–174, 1996.
- Paolo D'Alberto, A. Nicolau, "R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks", Algorithmica 47 (2) (2007) pp. 203-213.
- Gayathri Venkataraman,Sartaj Sahni,and srabani Mukhopadhyaya,"A Blocked All Pairs Shortest-Paths Algorithm"
- Sungchul Han and Sukchan Kang,"Optimizing All-Pairs Shortest-Path Algorithm Using Vector Instructions"
Index Terms
Keywords