algorithm - 从一堆可能的路径中找到权重最小的路径

Question

我在家庭作业问题上需要一些帮助/指点。如果有人能指出正确的方向来解决这个问题，我将不胜感激:)

作业

"An angry bird named Mo is flying a long journey to exact his revenge on the pigs. To save energy for the fight, the bird will take advantage of jet streams that will lower his flying energy consumption. Before the flight, BirdHQ gave the bird an input file in the following format:

1. First line contains only 1 integer, which is the constant energy it takes to fly 1 mile WITHOUT jet streams.
2. Every subsequent line contains 3 space-separated integers: the start mile marker of the jet stream, the end mile marker of the jet stream, and lastly an integer denoting the overall energy needed to fly that jet stream’s distance.

For instance, the line “3 7 12″ means it takes 12 energy units to fly the 4 miles between miles 3 and 7.

Note that jet streams can overlap, but the bird cannot be on more than one jet stream at a time, and it cannot fly partial jet streams.

For simplicity, consider the end mile marker of the farthest jet stream as the end of the journey.

Write a python program that takes in an input file “jetstreams.txt” to plan out the optimal sequence of jet streams Mo should fly on to minimize his energy consumption throughout the entire journey. All integers in the input file are non-negative. As output, print out the mininum total energy and a list of tuples denoting the jet streams’ endpoints.

For example, given the sample jetstreams.txt, the minimum total energy needed to fly all 24 miles is 352 energy units, and the optimal sequence of jet streams is [(0,5), (6,11), (14,17), (19,24)]."

jetstreams.txt

50
0 5 10
1 3 5
3 7 12
6 11 20
14 17 8
19 24 14
21 22 2

这是否类似于求解图形的最短路径？

Answer 1

是的。

你有一条“根本不使用急流”的路径，它由编号为 0、1、3、5、6、7、11、14、17、19、21、22、24 的顶点组成。连接每个顶点的边的“权重”为 50* 距离 - 因此 0->1 边的权重为 50，1->3 边的权重为 100，等等。

然后，您有代表喷射流的附加边 - 一条从 0->5 加权 10，一条从 1->3 加权 5，等等。

它们共同构成了一个有向无环图 (DAG)。

现在你已经知道了，你可以应用通常的图遍历技术来找到从顶点 0 到顶点 24 的“最便宜”路径。