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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Algorithms of All Pair Shortest Path Problem

by Susmita
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 120 - Number 15
Year of Publication: 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 },
issue_date = { June 2015 },
volume = { 120 },
number = { 15 },
month = { June },
year = { 2015 },
issn = { 0975-8887 },
pages = { 1-6 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume120/number15/21300-3876/ },
doi = { 10.5120/21300-3876 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:06:16.102422+05:30
%A Susmita
%T Algorithms of All Pair Shortest Path Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 120
%N 15
%P 1-6
%D 2015
%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
  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition. The MIT Press, Sep. 2001.
  2. http://en. wikipedia. org/wiki/Floyd%E2%80%93Warshall_algorithm
  3. 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
  4. 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.
  5. Hiroki Yanagisawa," A Multi-Source Label-Correcting Algorithm for the All-Pairs Shortest Paths Problem", RT0882,sept 2009.
  6. 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.
  7. 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.
  8. Gayathri Venkataraman,Sartaj Sahni,and srabani Mukhopadhyaya,"A Blocked All Pairs Shortest-Paths Algorithm"
  9. Sungchul Han and Sukchan Kang,"Optimizing All-Pairs Shortest-Path Algorithm Using Vector Instructions"
Index Terms

Computer Science
Information Sciences

Keywords

APSP Repeated Squaring Method ADD Based Algorithm Kleene's Algorithm Blocked Implementation

Powered by PhDFocusTM