REDUCED SOLUTION SET SHORTEST PATH PROBLEM: CAPTON ALGORITM WITH SPECIAL REFERENCE TO 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.