交通灯图

Question

假设您有一个标准图，并将值附加到每个节点和每个边缘。您希望在最短的时间内从图上的一个节点转到另一个节点。到目前为止，遍历此图所花费的时间将称为T。如果边的值为V，遍历该边将使您花费的时间增加V (T += V)。如果节点有一个值N，遍历该节点将迫使您等待，直到您花费的时间可被N (T += (N % 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

如你所见，底部要短得多。像这样的小尺寸更容易计算，但在城市大小时，您需要使用某种遍历算法。有谁知道除了暴力之外还有什么解决办法吗？

Answer 1

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