1. Perform uniform-cost search (UCS)on the graph. The start and goal nodes are labeled S and G, respectively. You must include the priority queue (showing when nodes are inserted/expanded), a cost-to-node, and a list of backpointers. Clearly specify the final path.

Here is psudocode to follow:

function UCS(problem) returns a solution/failure

initialize priority queue, cost to node, and backpointers

add starting node to priority queue

loop

if there are no nodes for expansion then return failure

pop the first node from the priority queue

if node contains goal state then return solution

for each available action

determine child node for given action

if child node has not been visited yet

add child node to priority queue and update cost

add parent node as backpointer to child node

else if child node has been visited but with higher cost

replace child node cost in priority queue to new value

replace backpointer to child node with new parent node