Suppose you live far from work and are trying to determine t

Suppose you live far from work and are trying to determine the best route to drive from your hometo your workplace. In order to solve this problem, suppose further that you have downloaded, froma 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 oftime that it takes to traverse each edge. So you have found another website that has a function,fi,j, dened for each edge, e = i, j, in G, such that each fi,j maps a time of day, t, to the amountof 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. Inaddition, we assume that you will be leaving for work in the morning and you live close enough toyour workplace so that you can get there before midnight. Moreover, the fi,j functions are denedto satisfy the normal rules of trac ow, 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 t1 < t2, then

fi,j(t2) + t2 t1 > fi,j(t1).
Describe an ecient algorithm that, given G and the fi,j functions for its edges, can determine, forany given time, t0, that you might leave your home in the morning, the amount of time requiredfor you to drive to work. What is the running time of your algorithm?

Solution

It\'s a Dynamic Programming Question, you\'ll have to check for all time after t0 you can start travelling and reach there in minimum time.
Keep an array D[i][j][t] which tells us the minimum required time to travel from i-j if leaves at time t.

For all time try to minimize values of this array with iteration:

D[i][j][t]>D[i][k][t]+f[k][j][D[i][k][t]] -- This tells us if time required to travel to k and then travel k-j after reaching there is less than time required to travel directly to i-j than update minimum time of D[i][j][t].

Time complexity would be O(n^2*timeUnit)