1(40pts) You are searching on a website for a cheap flight from Omaha (O) to Tok
ID: 3916092 • Letter: 1
Question
1(40pts) You are searching on a website for a cheap flight from Omaha (O) to Tokyo (T). The website is ready for action. Here are the possible routes: Omaha to Chicago (C) or Denver (D), and then Chicago to Tokyo directly or by way of either San Francisco (S) or Los Angeles (L), or Denver-San Francisco-Tokyo or Denver-Los Angeles-Tokyo. Let Pij denote the lowest price between the allowed city i and city j above. (a) Set up a Dynamic Programming problem in diagram for finding the lowest fares. (b) Find solution to the problem either graphically or algebraically.Explanation / Answer
We can use topological sorting of the graph.
The topological sorting of vertices here is 0, 1, ..., N-1.
Following is the basic code once topological sorting is known.
below code is to first calculate minimum cost for route 1, then for route 2, and so on.
These costs are stored in an array destination[0...N-1].
1) The minimum cost for route 0 is 0, i.e., destination[0] = 0
2) The minimum cost for route 1 is cost[0][1], i.e., destination[1] = cost[0][1]
3) The minimum cost for route 2 is minimum of following two.
1) destination[0] + cost[0][2]
2) destination[1] + cost[1][2]
3) The minimum cost for route 3 is minimum of following three.
1) destination[0] + cost[0][3]
2) destination[1] + cost[1][3]
3) destination[2] + cost[2][3]
Similarly, destination[4], destination[5], ... destination[N-1] are calculated.
//Let me know in case you face any difficulty
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.