(Alternative version of Dijkstra algorithm) An alternative version of the Dijkstra algorithm can be described as follows:

(Alternative version of Dijkstra algorithm) An alternative version of the Dijkstra algorithm can be described as follows:

The algorithm uses cost[v] to store the cost of a shortest path from vertex v to the source vertex s. cost[s] is 0. Initially assign infinity to cost[v] to indicate that no path is found from v to s. Let V denote all vertices in the graph and T denote the set of the vertices whose costs are known. Initially, the source vertex s is in T. The algorithm repeatedly finds a vertex u in T and a vertex v in V – T such that cost[u] + w(u, v) is the smallest, and moves v to T. The shortest path algorithm given in the text coninously update the cost and parent for a vertex in V – T. This algorithm initializes the cost to infinity for each vertex and then changes the cost for a vertex only once when the vertex is added into T. Implement this algorithm and use Listing 29.7, TestShortestPath. java, to test your new algorithm.