For the question, please write out the algorithm, prove its optimality, and analyze its complexity. (Hint: this algorithm could be a modification of Dijkstra algorithm). Thanks!

Your friends are planning an expedition to a small town deep in the Canadian

north next winter break. Theyve researched all the travel options

and have drawn up a directed graph whose nodes represent intermediate

destinations and edges represent the roads between them.

In the course of this, theyve also learned that extreme weather causes

roads in this part of the world to become quite slow in the winter and

may cause large travel delays. Theyve found an excellent travel Website

that can accurately predict how fast theyll be able to travel along the

roads; however, the speed of travel depends on the time of year. More

precisely, the Web site answers queries of the following form: given an

edge e = (v, w) connecting two sites v and w, and given a proposed starting

time t from location v, the site will return a value fe(t), the predicted

arrival time at w. The Web site guarantees that fe(t) ? t for all edges e

and all times t (you cant travel backward in time), and that fe(t) is a

monotone increasing function of t (that is, you do not arrive earlier by

starting later). Other than that, the functions fe(t) may be arbitrary. For

example, in areas where the travel time does not vary with the season,

we would have fe(t) = t + e, where e is the time needed to travel from the

beginning to the end of edge e.

Your friends want to use the Website to determine the fastest way

to travel through the directed graph from their starting point to their

intended destination. (You should assume that they start at time 0 and

that all predictions made by the Website are completely correct.) Give a

polynomial-time algorithm to do this, where we treat a single query to

the Website (based on a specific edge e and a time t) as taking a single

computational step.