有没有比Dijkstra算法更好的方法来找到不超过指定成本的最快路径

Question

我在寻找不超过指定成本的最快路径时遇到问题。有一个类似的问题，但他们之间有很大的区别。在这里，数据中唯一可以出现的记录是从较低的点到较高的点的记录(例如，1->3可能出现，3->1可能不出现)(见下文)。在不知情的情况下，我会使用Dijkstra。这些额外的信息可能会让它在比Dijkstras算法更快的时间内完成。你觉得怎么样？

假设我有指定的最高成本和4张记录。

// 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)点(当没有比我们现有成本更低的路径时，或者当1-5之间没有联系时，这是不可能的)，如果有，进入那里的最快方法是什么。

此类数据的输出为：

80 // fastest time
3 1 // number of points that (1 -> 2)  -> (2 -> 5)

请记住，如果有记录表明您可以移动1->2

1 2 30 5

它不允许你移动2&lt-1。

Answer 1

对于深度n处的每个节点，其路径的最小代价是n/2 * (minimal first edge at the path + minimal edge connecting to the node)-算术级数的和。如果此计算超过了所需的最大值，则无需检查后面的节点。切断这些节点并在其余节点上应用Dijkstra。