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

An Efficient Scheme for the Single Source Shortest Path Problem based on Dijkstra and SPFA Methodologies

by G.L. Prajapati, Pulkit Singhal, Ayush Ranjan Sharma, Neelesh Chourasia
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 163 - Number 8
Year of Publication: 2017
Authors: G.L. Prajapati, Pulkit Singhal, Ayush Ranjan Sharma, Neelesh Chourasia
10.5120/ijca2017913694

G.L. Prajapati, Pulkit Singhal, Ayush Ranjan Sharma, Neelesh Chourasia . An Efficient Scheme for the Single Source Shortest Path Problem based on Dijkstra and SPFA Methodologies. International Journal of Computer Applications. 163, 8 ( Apr 2017), 46-52. DOI=10.5120/ijca2017913694

@article{ 10.5120/ijca2017913694,
author = { G.L. Prajapati, Pulkit Singhal, Ayush Ranjan Sharma, Neelesh Chourasia },
title = { An Efficient Scheme for the Single Source Shortest Path Problem based on Dijkstra and SPFA Methodologies },
journal = { International Journal of Computer Applications },
issue_date = { Apr 2017 },
volume = { 163 },
number = { 8 },
month = { Apr },
year = { 2017 },
issn = { 0975-8887 },
pages = { 46-52 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume163/number8/27419-2017913694/ },
doi = { 10.5120/ijca2017913694 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:09:41.430676+05:30
%A G.L. Prajapati
%A Pulkit Singhal
%A Ayush Ranjan Sharma
%A Neelesh Chourasia
%T An Efficient Scheme for the Single Source Shortest Path Problem based on Dijkstra and SPFA Methodologies
%J International Journal of Computer Applications
%@ 0975-8887
%V 163
%N 8
%P 46-52
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper presents detailed comparisons and analysis of various single source shortest path algorithms. The paper proposes comparison among these algorithms on the basis of execution time taken by the algorithms to completely find the shortest path to all the nodes from a starting node. The algorithms have been analyzed on the various parameters: number of vertices, number of edges, and structure of the graph. This analysis will help in selecting the appropriate algorithm to be used in solving a particular real-life problem. This paper also proposes an algorithm that works efficiently over all types of the graph.

References
  1. ShortestPathProblem,http://en.wikipedia.org/wiki/Shortest_path_problem
  2. Bellman ford (1958). “On a routing problem”. Quarterly of Applied Mathematics. 16: 87-90.Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik.
  3. Faster Dijkstra on Special Graphs, http://codeforces.com/blog/entry/43508.
  4. Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming: Series A and B, v.73 n.2, p.129-174, May 31, 1996.
  5. Shortest Path Faster Algorithm, http://codeforces.com/blog/entry/16221.
  6. Prüfer, H. "Neuer Beweis eines Satzes über Permutationen." Arch. Math. Phys. 27, 742-744, 1918.
  7. Construction of Special Graphs for poor performance of SPFA, http://codeforces.com/blog/entry/16221?#comment-211370
  8. 9th DIMACS Implementation Challenge - Shortest Paths, http://www.dis.uniroma1.it/challenge9/download.shtml
  9. Stanford Network Analysis Project, https://snap.stanford.edu/
Index Terms

Computer Science
Information Sciences

Keywords

Single Source Shortest Path Execution Time Performance Analysis

Powered by PhDFocusTM