1

假设您有一个标准图，每个节点和每条边都有附加值。您希望在最短的时间内从图表上的一个节点转到另一个节点。到目前为止，您遍历此图所花费的时间将被称为 T。如果边的值为 V，则遍历该边会将 V 添加到您花费的时间 (T += V)。如果一个节点的值为 N，遍历该节点将迫使您等待，直到您花费的时间可以被 N 整除 (T += (N - T % N) % N)。

你可以把它想象成街道和红绿灯。在街道上行驶需要一定的时间才能到达另一端。开车穿过红绿灯需要等待它变绿的时间。

例如，假设您有这个图表：

S--6--[1]--2--[7]
       |       |
       3       2
       |       |
      [9]--3--[6]--1--E

乍一看，顶部路径看起来更快，因为它具有更短的边缘和更短的延迟。然而，事实证明底部路线更快。让我们先计算底部：

Start: 0 + 6 -> 6
       6 % 1 == 0 # We can pass
       6 + 3 -> 9
       9 % 9 == 0 # We can pass
       9 + 3 -> 12
       12 % 6 == 0 # We can pass
       12 + 1 -> 13
End:   13

然后是顶部：

Start: 0 + 6 -> 6
       6 % 1 == 0 # We can pass
       6 + 2 -> 8
       8 % 7 != 0 # Have to wait
       8 + 6 -> 14
       14 % 7 == 0 # We can pass
       14 + 2 -> 16
       16 % 6 != 0 # Have to wait
       16 + 2 -> 18
       18 % 6 == 0 # We can pass
       18 + 1 -> 19
End:   19

如您所见，底部要短得多。在这样的小规模下，计算起来更容易，但在城市规模下，您需要使用某种遍历算法。有谁知道除了蛮力之外是否有任何解决方案？

4

1 回答 1

2

它被称为最短路径搜索问题，可以用 Dijkstra 算法在多项式时间内解决。计算路径长度时，还应添加在目标顶点等待的时间（目标顶点除外）。所以它仍然是最短路径搜索问题，但权重函数与简单边的权重和略有不同。

于 2014-10-13T21:01:13.830 回答