The getShortestPath method finds a u with the smallest cost[u] using a linear search, which takes O( |V| ). The search time can be reduced to O(log|V| ) using an AVL tree. Modify the method using an AVL tree to store the vertices in V–T. Use Listing 29.7, Test- ShortestPath.java, to test your new implementation.

Data from Listing 29.7,

Transcribed Image Text:

Input: a graph G = (V. E) with nonnegative weights Output: a shortest-path tree with the source vertex s as the root 1 ShortestPathTree getShortestPath(s) ( 2 Let T be a set that contains the vertices whose paths to s are known; Initially T is empty: Set cost[s] = 0; and cost [v] = infinity for all other vertices in V: 3 4 6 wh1le (size of T< n) { Find u not in T with the smallest cost [u]: Add u to T: for (each v not in T and (u. v) in E) if (cost[v] > cost[u] + w (u, v)) { cost [v] = cost[u] + w(u, v): parent[v] = u; 7 8 9 10 11 12 13 14 }