2

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

4

1 回答 1

1

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

于 2012-11-16T10:41:37.383 回答