带约束的最短路径算法
带约束的最短路径算法
提问于 2014-05-27 04:48:30
我想解决一个变化的最短路径算法。我不知道如何处理额外的约束。
很少给出城市
(<=50)和两个(N * N)矩阵，它们分别表示城市之间的旅行时间和城市之间的收费。现在，给定时间t(<10000)，我们必须选择一条从城市0到城市N-1的道路，这样收费成本最低，并且我们在给定的时间内完成了t的旅行。
我知道，只有一个参数，例如时间，我们可以使用最短路径算法，如Bellman–Ford algorithm或Dijkstra's algorithm。但是如何修改它以包含两个约束呢？如何制定解决问题的动态规划方案？
我试图用DP +完全搜索来解决这个问题。我是在正确的方向上，还是有比这些方法更好的算法？
回答 1
Stack Overflow用户
发布于 2014-05-27 08:44:02
对于这个问题，可以使用Dijkstra，首先您需要创建一个状态图，每个状态代表城市和时间离开的。因此，在每个州(城市A，时间t)和状态(城市B，时间t1)之间，只有在给定时间是(t1 -t)的情况下，才能从城市A移动到城市B。每条边的价值都是代价。使用标准Dijkstra解决这个问题很简单。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23881248
复制相关文章
相似问题
腾讯云开发者
