Suppose that a startup is building a competitor to Google Maps. This startup notices that travel...

 

Transcribed Image Text:

Suppose that a startup is building a competitor to Google Maps. This startup notices that travel time on a road is determined not only by a road's length, but also by many time dependent factors such as traffic, weather, visibility, maintenance, etc. Their database models locations and roads as a directed graph G= (V,E). Each edge e e E can be queried with a time of day t as f(e, t) to obtain the predicted time to traverse edge e starting at time t. The startup wants to identify the fastest routes in their graph. Modify Dijkstra's algorithm for Shortest Path using calls to the query function f to find the fastest routes to all other nodes starting at a start node s V at time t = 0. Briefly justify your algorithm's correctness. Suppose that a startup is building a competitor to Google Maps. This startup notices that travel time on a road is determined not only by a road's length, but also by many time dependent factors such as traffic, weather, visibility, maintenance, etc. Their database models locations and roads as a directed graph G= (V,E). Each edge e e E can be queried with a time of day t as f(e, t) to obtain the predicted time to traverse edge e starting at time t. The startup wants to identify the fastest routes in their graph. Modify Dijkstra's algorithm for Shortest Path using calls to the query function f to find the fastest routes to all other nodes starting at a start node s V at time t = 0. Briefly justify your algorithm's correctness.