REDUCED SOLUTION SET SHORTEST PATH PROBLEM: CAPTON ALGORITM WITH SPECIAL REFERENCE TO DIJKSTRA’S ALGORITHM

Authors

  • Qaiser Abbas Department of Computer Science & Information Technology, University of Sargodha, 40100, Sargodha, PK
  • Qasim Hussain Department of Computer Science & Information Technology, University of Sargodha, 40100, Sargodha, PK
  • Tehseen Zia Department of Computer Science & Information Technology, University of Sargodha, 40100, Sargodha, PK
  • Arfan Mansoor Institut für Informationstechnik, Technische Universität Ilmenau, Ilmenau, Thuringia, DEU

DOI:

https://doi.org/10.22452/mjcs.vol31no3.1

Keywords:

Shortest Path Problem, Reduction Factor, Reduce Solution Set, Capton Algorithm, Heuristic Distance, Dijkstra’s Algorithm

Abstract

To find the shortest path between the nodes of a graph, different algorithms like Bellman-Ford, Dijkstra, Floyd-Warshall and Johnson exist. However, in this paper, the issue of shortest path problem with special reference to Dijkstra’s algorithm is presented. An idea of shortlisting the appropriate nodes in a graph is proposed and presented, which is then used to find the shortest path with the help of Dijkstra’s algorithm. This complete work -named Capton algorithm- provides a solution to single source shortest path problem with minimized time complexity as compared to Dijkstra’s algorithm. 

Downloads

Download data is not yet available.

Downloads

Published

2018-07-30

How to Cite

Abbas, Q., Hussain, Q., Zia, T., & Mansoor, A. (2018). REDUCED SOLUTION SET SHORTEST PATH PROBLEM: CAPTON ALGORITM WITH SPECIAL REFERENCE TO DIJKSTRA’S ALGORITHM. Malaysian Journal of Computer Science, 31(3), 175–187. https://doi.org/10.22452/mjcs.vol31no3.1

Issue

Vol. 31 No. 3 (2018): Malaysian Journal of Computer Science

Section

Articles