(Solved): 3. Rewrite algorithm Shortest Paths under the following assumptions: (a) G is represented by its ad ...

3. Rewrite algorithm Shortest Paths under the following assumptions: (a) G is represented by its adjacency lists. The head nodes are HEAD(1),..., HEAD(n) and each list node has three fields: VER- TEX, COST, and LINK. COST is the length of the corresponding edge and n the number of vertices in G. (b) Instead of representing S, the set of vertices to which the shortest paths have already been found, the set T = V(G)-S is repre- sented using a linked list. What can you say about the computing time of your new algorithm relative to that of Shortest Paths? 1 Algorithm Shortest Paths(v, cost, dist, n) 2 3 // dist[j], 1?j?n, is set to the length of the shortest // path from vertex v to vertex j in a digraph G with n // vertices. dist[v] is set to zero. G is represented by its // cost adjacency matrix cost[1: n, 1:n]. 4 5 6 { 7 for i:=1 to n do 8 { // Initialize S. 9 S[i] = false; dist[i]:= cost [v, i]; 10 } 11 S[v]:= true; dist[v] := 0.0; // Put v in S. for num = 2 to n - 1 do 12 13 { 14 15 // Determine n - 1 paths from v. Choose u from among those vertices not in S such that dist[u] is minimum; S[u]:= true; // Put u in S. 16 17 18 for (each w adjacent to u with S[w] = false) do // Update distances. 19 20 if (dist[w] > dist[u] + cost[u, w])) then dist[w]: dist[u] + cost[u, w]; 21 = 22 } 23 }