GOAL STATE IS 6.

Consider the following algorithm to find the shortest distance between two cities (S rightarrow G) Step 1: Maintain a list of cities C that you have visited sc far. Cache the total path-cost g(c) and the predecessor city p(c) for every city c in C Step 2: Maintain a list of neighboring cities F (the fringe) that are not in C. C n f = 0 Cache the total path-cost g(f) and the predecessor city p(f) for every city f in F Cities in F are ordered according to their total path cost g(f) Step 3: At every iteration of the algorithm, starting at 5, visit the city in the fringe that has the lowest path-cost. Add it to C 3nd remove it from f| Step 4: Add all new neighboring cities (including their g(f) and p(f)} into the fringe that are not already in C. (it is possible to have copies in F with different predecessors). Step 5: if more than l copy of a city is in the fringe, only retain the one with lowest g(f). Delete all other copies. Step 6: IF you reach G, reconstruct the path from 5 rightarrow G and report g(G) and the path. Answer the following questions: a. Work out the first 3 steps of the algorithm This means: visit and expand the first 3 nodes starting at 0. use the graph above. *'0M is the source and "6*' is the goal. b. Is this algorithm an instance of an informed or an uninformed search algorithm? (Explain) c. Is this algorithm an instance of a tree search or graph search algorithm? (Explain) d. is this algorithm complete? (Explain) e. is this algorithm optimal? (Explain)