An alternative version of the Dijkstra algorithm can be described as follows: The algorithm uses cost[v] to

Question:

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 continuously updates 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.

Data from Listing 29.7,