Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More

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

Print
PDF
 
Download Full Text
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 and 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):46-52, April 2017. BibTeX

@article{10.5120/ijca2017913694,
	author = {G.L. Prajapati and Pulkit Singhal and Ayush Ranjan Sharma and 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 = {April 2017},
	volume = {163},
	number = {8},
	month = {Apr},
	year = {2017},
	issn = {0975-8887},
	pages = {46-52},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume163/number8/27419-2017913694},
	doi = {10.5120/ijca2017913694},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, 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/

Keywords

Single Source Shortest Path, Execution Time, Performance Analysis