Suppose we are trying to implement a program that finds a shortest path between any two locations within Seattle In case of a tie, the program should find us the route with the fewest vertices on the path. For example, suppose we are considering two different routes from UW to the Space Needle. Both routes are 3 miles long, but route one has 3 vertices and route two has five vertices. In this case, our algorithm should pick route one (a) (7 points) Explain how you would model this scenario as a graph. Answer the following questions in bullet points with short sentences, then give an overall description on anything else that is relevant: i. What are your vertices and edges? i. What information do you store for each vertex and edge? ii. Is this a weighted graph or an unweighted one? iv. Is this a directed or undirected graph? v. Do you permit self-loops? Parallel edges? (b) (3 points) At a high-level, how you would modify Dijkstra's algorithm to find us the best route according i. How you combine or use different factors like road length and number of vertices in the path while ii. How you would modify Dijkstra's algorithm to break ties in the manner described above. (State which to the specifications listed above. In particular, be sure to explain: finding the best route. lines you would modify, if any, and/or lines you would add to the following pseudocode; state how and when you would check and resolve ties, e.g., during the BFS search or after the BFS search) Use the following pseudocode for Dijkstra's algorithm as a base for your response to this question; t will be helpful to list specific lines that you will be modifying to fit this specific problem. Be sure your algorithm makes sense when combined with the graph representation you chose in part a. Answer in English (not code or pseudocode) and in at most a few sentences Answers significantly longer than required will not receive full credit : function Dijkstra(Graph G, Vertex source) 2: nitialize distances to oo 3: mark source as distance 0 4: mark all vertices unprocessed 5: while there are unprocessed vertices do 6: 7: 8: 9- let u be the closest unprocessed vertex for each edge (u, v) leaving u do if u.dist + w(u, v)