Imagine you graduated and got a job at stingyflights.com. Your task is to design

Question

Imagine you graduated and got a job at stingyflights.com. Your task is to design an algorithm for finding cheap flights. You are given a list of n cities, and a list of m flights between them. For each flight i, you are given its departure city xi , its destination city yi , its departure time ti , its duration di , and its cost ci . So flight i departs from city xi at time ti , arrives at city yi at time ti + di , and costs ci dollars. Design an algorithm that given a pair of cities a, b, computes the cheapest possible route (i.e. sequence of flights) that starts at a at time 0, and ends at b at time at most T. The running time of your algorithm should be polynomial in n and m (e.g. O(n 10m5)).

Hint: Express the above problem as shortest-path computation in some graph.

Explanation / Answer

We can use Dijkstra’s algorithm in this case.

Following is complete algorithm for finding shortest distances.
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if ((dist[v] > dist[u] + weight(u, v)) AND (t[v]>ct) AND (ct+d[v]<=T) )
………………………dist[v] = dist[u] + weight(u, v)
………………………par[v] = u
………………………ct+=d[v]

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.