假设您有一个标准图，其中的值附加到每个节点和每个边。
您希望在最短的时间内从图上的一个节点转到另一个节点。
到目前为止，遍历这个图所花费的时间称为t。
如果一条边的值为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
如你所见，底部要短得多。
在像这样的小规模下，计算起来比较容易，但是在城市规模下，您需要使用某种遍历算法。
有人知道除了暴力还有什么办法吗？
最佳答案
它被称为最短路径搜索问题，可以用Dijkstra算法在多项式时间内求解计算路径长度时，还应添加在目标顶点等待的时间（目标顶点除外）。因此它仍然是最短路径搜索问题，但权值函数与简单边的权值和略有不同。
关于algorithm - 交通灯图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26348784/