2. [A* Search Algorithm.] C 3 A 2 8 S E m Consider the above undirected weighted graph G = (VE). (a) Suppose we run Dijk

[answerhappygod]

2 A Search Algorithm C 3 A 2 8 S E M Consider The Above Undirected Weighted Graph G Ve A Suppose We Run Dijk 1 (27.42 KiB) Viewed 90 times

2. [A* Search Algorithm.] C 3 A 2 8 S E m Consider the above undirected weighted graph G = (VE). (a) Suppose we run Dijkstra's algorithm from class to find the minimum-weight path from Sto T starting from node S. List the nodes visited by the Dijkstra's algorithm in the order of when they are first marked "Sure" by the algorithm, breaking any tie by alphabetical order. Note that the algorithm should stop when node T is marked "sure". [We are expecting: A list of vertices from G that are visited by the Dijkstra's algorithm in the order of when they are first marked "sure".] (b) In the above run of the Dijkstra's algorithm, we visited all nodes in the graph before finding out the shortest path between S and T. Suppose we want to make the algorithm even more efficient by visiting less nodes. Luckily, at each vertex vin G, we have a rough estimate h() of how far it is from vertex v to vertex T. The value of h() is denoted near each vertex in the following graph. Recall that in Dijkstra's algorithm, we use our estimate of the distance from S to v, denoted d[v] to select the 'not sure' node to visit in each iteration. Now with our rough estimates of the distances to T, we modify the algorithm such that we use d"[v] = d[v] + "[v] instead of d[v] to choose the next not-sure' node. Rerun this modified Dijkstra's algorithm to search for shortest S-T paths starting from node S, and give a list of vertices visited by the algorithm in the order of when they are first marked "sure".

C(9) 3 F(6) A(10) 1 2 8 S(7) D(8) T(0) 3 E(3) B(6) [We are expecting: A list of vertices from G that are visited by the Dijkstra's algorithm in the order of when they are first marked "sure".]