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

Parallelization of Shortest Path Finder on GPU: Floyd-Warshall

by Dhananjay Kulkarni, Neha Sharma, Prithviraj Shinde, Vaishali Varma
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 118 - Number 20
Year of Publication: 2015
Authors: Dhananjay Kulkarni, Neha Sharma, Prithviraj Shinde, Vaishali Varma
10.5120/19398-0920

Dhananjay Kulkarni, Neha Sharma, Prithviraj Shinde, Vaishali Varma . Parallelization of Shortest Path Finder on GPU: Floyd-Warshall. International Journal of Computer Applications. 118, 20 ( January 2015), 5-8. DOI=10.5120/19398-0920

@article{ 10.5120/19398-0920,
author = { Dhananjay Kulkarni, Neha Sharma, Prithviraj Shinde, Vaishali Varma },
title = { Parallelization of Shortest Path Finder on GPU: Floyd-Warshall },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 118 },
number = { 20 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 5-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume118/number20/19398-0920/ },
doi = { 10.5120/19398-0920 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:02:13.001350+05:30
%A Dhananjay Kulkarni
%A Neha Sharma
%A Prithviraj Shinde
%A Vaishali Varma
%T Parallelization of Shortest Path Finder on GPU: Floyd-Warshall
%J International Journal of Computer Applications
%@ 0975-8887
%V 118
%N 20
%P 5-8
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The project deals with implementation of Floyd Warshall Algorithm i. e All Pair Shortest Path. This algorithm is implemented using parallel programming concept for faster solution. This is a research based project in which the serial and parallel computations are compared. Floyd Warshall algorithm has overcome the drawbacks of Dijkstra's and Bellman Ford Algorithm. For parallel programming, the project is implemented using NVIDIA GPU(NVIDIA GeForce 820M , 410M) for which CUDA(CUDA Toolkit 6. 0) is used . The purpose of developing this project is to find the shortest path between all the present nodes in a graph. This system is designed to work on a large dataset(set of 48 or 72 or 100 cities). This project can be implemented for Airline Systems,Transportation services, Courier Services, Networking.

References
  1. Jian Ma ; Sch. of Transp. Eng. , Tongji Univ. , Shanghai, China ; Ke-Ping Li ; Li-yan Zhang, A Parallel Floyd-Warshall algorithm based on TBB, IEEE.
  2. http://ati. amd. com/products/streamprocessor/index. html
  3. John D. owens, David Luebke, Naga Govindaraju, Mark Harris, Jens Kruger, Aaron E. Lefohn, Timothy. Purcell,A survey of general-purpose computation on graphics hardware, Computer Graphics Forum 34(March) (2007)80-113.
  4. Kairanbay Magzhan, Hajar Mat Jani"A review and evaluation of shortest path algorithms".
  5. Olaf Schenk,Matthias Christen,Helmar Burkhart"J. Parallel Distrib. Comput".
  6. http://www. nvidia. com/object/what-is-gpu-computing. html
  7. Efficient multi GPU algorithm for All pair shortest path.
  8. G. Venkataraman, S. Sahni, and S. Mukhopadhyaya, A blocked all-pairs shortest-paths algorithm, J. Exp. Algorithmics.
  9. P. Harish and P. Narayanan, Accelerating large graph algorithms on the GPU using CUDA, Lecture Notes in Computer Science
  10. A. Buluc, J. R. Gilbert, and C. Budak, Solving path problems on the GPU, Parallel Computing, vol. In Press, Corrected Proof, 2009.
  11. R. Seidel. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences
  12. U. Bondhugula, A. Devulapalli, J. Fernando, P. Wyckoff, and P. Sadayappan, Parallel fpga-based all-pairs shortest-paths in a directed graph, Parallel and Distributed Processing Symposium, International
Index Terms

Computer Science
Information Sciences

Keywords

Floyd Warshall Algorithm Parallel Programming CUDA NVIDIA GPU.

Powered by PhDFocusTM