问题描述
我在使用发现，不超过规定的成本最快的路径问题。有类似的问题，这一个，但有它们之间有很大的区别。在这里，可以出现在数据中的唯一记录是那些，从一个较低的点，导致一个较高的点（例如，1 - > 3可能出现，但3 - > 1可能不）（见下文）。如果不知道，我会使用Dijkstra算法。这更多的信息，可能会让它在时间比Dijkstras算法做得更快。你觉得呢？
I'm having a problem with finding fastest path that do not exceed specified cost.There's similar question to this one, however there's a big difference between them.Here, the only records that can appear in the data are the ones, that lead from a lower point to a higher point (eg. 1 -> 3 might appear but 3 -> 1 might not) (see below). Without knowing that, I'd use Dijkstra. That additional information, might let it do in a time faster than Dijkstras algorithm.What do you think about it?
比方说，我已经有了规定的最大成本，以及4条记录。
Let's say I've got specified maximum cost, and 4 records.
// specified cost
10
// end point
5
//(start point) (finish point) (time) (cost)
2 5 50 5
3 5 20 9
1 2 30 5
1 3 30 7
// all the records lead from a lower to a higher point no.
我必须决定，是否有可能从点得到（1）至（5）（它不可能孤单的时候，成本和LT没有路，不等于我们已经有了或者孤单的时候1-5之间没有连接）和如果是这样，这将是在那里得到的最快方法。
I have to decide, whether It's possible to get from point (1) to (5) (its impossible when theres no path that costs <= than we've got or when theres no connection between 1-5) and if so, what would be the fastest way to get in there.
对于这样的数据将输出：
The output for such data would be:
80 // fastest time
3 1 // number of points that (1 -> 2) -> (2 -> 5)
请记住，如果有一个记录，指出可以移动的 1> 2
Keep in mind, that if there's a record saying you can move 1->2
1 2 30 5
它不使您可以移动 2'。-1
推荐答案
对于每个节点的深度为n，路径到它的最低成本为 N / 2 *（最小的首先在道路边+最小边连接到节点） - 等差数列的求和。如果该计算超过所需的最大，无需检查后面的节点。切断这些节点关闭，应用Dijkstra算法就休息了。
For each node at depth n, the minimum cost of path to it is n/2 * (minimal first edge at the path + minimal edge connecting to the node) - sum of arithmetic series. If this computation exceeds the required maximum, no need to check the nodes that follow. Cut these nodes off and apply Dijkstra on the rest.
这篇关于有没有比Dijkstra算法寻找不超过规定的成本最快的路径更好的办法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！