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

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