我想解一个变异的最短路径算法。我不知道如何处理额外的限制。
给出了几个城市
(<=50)和两个(N * N)矩阵表示城市间的旅行时间和城市间的通行费。现在给一次t(<10000)，我们必须选择一条路径从城市0到达到N-1，这样通行费最少，我们就完成了旅行在给定时间内t.
我知道只有一个参数，比如只有时间，我们可以使用Bellman–Ford algorithm或Dijkstra's algorithm这样的最短路径算法。但是如何修改它以包含两个约束呢?如何对问题进行动态规划求解?
我正在尝试用DP +完全搜索来解决它。我的方向是对的吗，还是有比这些方法更好的算法?
可以使用Dijkstra解决这个问题，首先您需要创建一个包含每个状态的状态图表示所在城市和剩余时间。因此，在每个状态(城市A，时间t)和状态(城市B，时间t1)之间，如果你能在给定的时间(t1 - t)内从城市A移动到城市B，就只能有一条边，而每条边的值就是通行费。使用标准Dijkstra解决这个问题很简单。