Single source shortest path algorithm Dijkstra and Bellman-Ford Algorithms: A Comparative study

  • Abdul Manan, Syed Imran Ali Lakyari
Keywords: GIS (Geographic Information Systems), optimal path, Shortest Path Algorithm, Longest path problem, Reliable path problems

Abstract

The “shortest path problem” is about finding a path between two vertices in a graph such that the total sum of the edges weights is minimum. Shortest-path problems are the most fundamental and the most commonly faced problems in the study of transportation and communication networks and In GIS Application [1, 2, and 5]. This is especially evident in the event that we sum up the class of “shortest path problems” to incorporate related problems, for example, the “longest-path problem”, the “most-reliable-path problems”, the “largest-capacity-path problem”, and various “routing problems”. Along these lines it isn't astounding that an enormous number of papers, reports, and expositions have been distributed regarding the matter of “shortest-path algorithms”. There have additionally seemed various astounding studies, review paper. There are many algorithms to find shortest path like Dijkstra, Bellman-ford, Floyd-Warshal, A*, Johnsons Algorithm, Viterbi Algorithm etc. In this paper we will discuss and examine Dijkstra and Bellman-ford algorithms and we will suggest by our study that in which situation which algorithm is best.

Downloads

Download data is not yet available.
Published
2020-06-30
How to Cite
Abdul Manan, Syed Imran Ali Lakyari. (2020). Single source shortest path algorithm Dijkstra and Bellman-Ford Algorithms: A Comparative study. International Journal of Computer Science and Emerging Technologies , 3(2), 25-28. Retrieved from http://ijcet.salu.edu.pk/index.php/IJCET/article/view/48