Suppose you live far from work and are trying to determine the best route to drive from your home to your workplace. In order to solve this problem, suppose further that you have downloaded, from a government website, a weighted graph, G, representing the entire road network for your state. Although the edges in G are labeled with their lengths, you are more interested in the amount of time that it takes to traverse each edge. So you have found another website that has a function, f_i,j , defined for each edge, e = (i, j), in G, such that each f_i,j maps a time of day, t, to the amount of time it takes to go from i to j along the edge, e = (i, j), if you enter that edge at time t. Here, time is measured in minutes and times of day are measured in terms of minutes since midnight. In addition, we assume that you will be leaving for work in the morning and you live close enough to your workplace so that you can get there before midnight. Moreover, the f_i,j functions are defined to satisfy the normal rules of traffic flow, so that it is never possible to get to the end of an edge, (i, j), sooner than someone who entered that edge before you. That is, if t₁ < t₂, then 

Describe an efficient algorithm that, given G and the f_i,j functions for its edges, can determine, for any given time, t₀, that you might leave your home in the morning, the amount of time required for you to drive to work. What is the running time of your algorithm?

Transcribed Image Text:

fij(t2) + t2 – t1 > fij(t1)