Use the A* algorithm on the edge weighted graph above to find a shortest path from the vertex S to t and fill the table below accordingly. The first row provides the distance of every vertex from S after the initialization of the algorithm. Every subsequent row in the table corresponds to the status of the algorithm after another vertex has been removed from the priority queue and the corresponding updates (to the distances) have been applied. The first column provides the vertex that has currently been removed from the priority queue. Each subsequent column corresponds to one vertex and should provide the distance of the vertex from S as currently calculated by the algorithm. The whole first row is given as an example below.

Provide the remaining rows of the table as an answer to the sub-questions below. Every sub-question corresponds to one row and to provide the row use for infinity and a single blank symbol to separate the columns. For example, the first row that is already given in the table would have been provided by answering: - 0 . Note that the symbol "-" indicates that no vertex has been removed from the priority queue; but this only occurs for the first row corresponding to the initialization. All sub-sequent rows provided by you need to start with the name of the vertex that has been removed from the priority queue.

Give the following:

1)1st Row

2)2nd Row

3)3rd Row

4)4th Row

5)5th Row

6)6th Row

7) Shortest Path from S to t as a list of vertices seperated by a comma(,)

\begin{tabular}{c|c|c|c|c|c|c} Queue Element & S & a & b & c & d & t \\ \hline & 0 & & & & & \\ \hlineS & & & & & & \\ \hline & & & & & & \\ \hline \end{tabular}