algorithm - 寻找不超过指定成本的最快路径

Question

我在寻找不超过指定成本的最快路径时遇到问题。

假设我有指定的最大成本和 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

我必须决定，是否有可能从点 (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

使用动态规划，像这样:

Route(node, length, target, accumulated)

if length <= 0 return -1
if node == target return accumulated

For each adjacent node:
  current length = accumulated + Route(adjacent node, length - connecting edge weight, target, accumulated + connecting edge weight)
  min length = min(current length, min length)

return min length