4. The questions in this problem make use of the following weighted graph: 5 8 3 s 7 2 t 1 4 9 V (a) List all simple paths from s to w, along with their associated costs. (Note: A simple path is a path with no repeated vertices) To refer to a path, list the vertices in order in which they are encountered; for example, if you wanted to list the path from s to t along the top of the graph, you would write (suwt, 16). (b) Consider a form of depth first search that uses a greedy heuristic to decide which edge to traverse next from a given node. Once a node is selected for expansion, this approach orders the edges from that node by minimum cost. You can also assume this implementation of depth first search remembers previously-visited nodes and does not select edges that would visit them again. Starting from node s, what is the first path found from s to t and what is its cost? Is this the optimal path from s to t? If not, give the optimal path. (c) Using the version of depth first search described in (b), list the order in which depth first search visits all of the nodes if we start the algorithm from u