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

Question

我在寻找不超过指定成本的最快路径时遇到问题。有与this one类似的问题，但是它们之间存在很大差异。在这里，唯一可以出现在数据中的记录是从较低点到较高点的记录(例如，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<-1。

Answer 1

对于深度为 n 的每个节点，到它的路径的最小成本是 n/2 *(路径上的最小第一条边 + 连接到节点的最小边) - 算术级数的总和。如果此计算超过所需的最大值，则无需检查后面的节点。切断这些节点并在其余节点上应用 Dijkstra。