Suppose we are trying to implement a program that finds a path between any two locations within Seattle that takes the shortest amount of time possible. Note that the time needed to travel down a particular stretch of road depends on several different factors such as the length of the road, the speed limit, and the amount of traffic. In case of a tie, the program should find us the route with the shortest physical distance. For example, suppose we are considering two different routes from UW to the Space Needle. Based on current traffic conditions, both routes will take 15 minutes. However, route one is 3.5 miles long and route two is 3.7 miles long. In that case, our algorithm should pick route one. (a) Explain how you would model this scenario as a graph. In particular, be sure to answer the following questions: What are your vertices and edges? What information do you store for each vertex and edge? . Is this a weighted graph or an unweighted one? Is this a directed or undirected graph? Do you permit self-loops? Parallel edges? (b) Explain how you would modify Dijkstra's algorithm to find us the best route according to the specifications listed above. In particular, be sure to explain .How you combine or use different factors like road length, the speed limit, or the amount of traffic while finding the best route How you would modify Dijkstra's algorithm to break ties in the manner described above. (c) Suppose we want to modify our program so that the user and pick whether they want to take a car or walk to the given destination This changes what paths the user may take. For example, if the user is taking a car, they can travel along freeways but not through parks or alleyways. Conversely, if the user is walking, they can travel through parks and alleyways but not freeways Explain how you would implement this new feature. Do you need to make any changes to your model? Do you need to modify how you implement Dijkstra's algorithm? Suppose we are trying to implement a program that finds a path between any two locations within Seattle that takes the shortest amount of time possible. Note that the time needed to travel down a particular stretch of road depends on several different factors such as the length of the road, the speed limit, and the amount of traffic. In case of a tie, the program should find us the route with the shortest physical distance. For example, suppose we are considering two different routes from UW to the Space Needle. Based on current traffic conditions, both routes will take 15 minutes. However, route one is 3.5 miles long and route two is 3.7 miles long. In that case, our algorithm should pick route one. (a) Explain how you would model this scenario as a graph. In particular, be sure to answer the following questions: What are your vertices and edges? What information do you store for each vertex and edge? . Is this a weighted graph or an unweighted one? Is this a directed or undirected graph? Do you permit self-loops? Parallel edges? (b) Explain how you would modify Dijkstra's algorithm to find us the best route according to the specifications listed above. In particular, be sure to explain .How you combine or use different factors like road length, the speed limit, or the amount of traffic while finding the best route How you would modify Dijkstra's algorithm to break ties in the manner described above. (c) Suppose we want to modify our program so that the user and pick whether they want to take a car or walk to the given destination This changes what paths the user may take. For example, if the user is taking a car, they can travel along freeways but not through parks or alleyways. Conversely, if the user is walking, they can travel through parks and alleyways but not freeways Explain how you would implement this new feature. Do you need to make any changes to your model? Do you need to modify how you implement Dijkstra's algorithm