In most graph theory problems, the shortest path problem or SPP is the problem of determining a distance between two nodes (or vertices) in a weighted graph in order that the sum of the weights of its constituent edges is minimized. In a connected graph there exists at least one path between every pair of vertices. In a weighted graph, the path between a pair of vertices for which the sum of the weights of the constituent edges is minimum is called the shortest path between them. Here in this paper, we developed a new algorithm to determine the shortest path of a weighted graph which is an improvement over Dijkstra’s algorithm so as to obtain all the shortest paths of a given weighted graph. Let us first recollect Dijkstra’s algorithm so as to easily comprehend our result