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,

Input: a weighted graph G = (V. E) with nonnegative weights Output: A shortest-path tree from a source vertex s 1 ShortestPathTree getShortestPath(s) { 2 Let T be a set that contains the vertices whose paths to s are known: Initially T contains source vertex s with cost[s] = 0: for (each u in V - T) cost[u] = infini ty: 3 4 6 7 wh1le (size of T < n) { Find v in V - T with the smallest cost[u] + w(u. v) value 9