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.

(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. Use the following pseudocode for Dijkstra's algorithm as a base for your response to this question; it 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 Dijkstra(Graph G, Vertex source) ( a initialize distances to infinity mark source as distance 0 mark all vertices unprocessed while (there are unprocessed vertices) C let u be the closest unprocessed vertex foreach (edge (u, v) leaving u) C if (u.dist w(u, v)