有一些限制的最短路径算法
我想解决最短路径算法的变体。 我无法弄清楚如何处理额外的限制。
很少有城市(<=50)连同两个(N * N)矩阵表示城市之间的旅行时间和城市之间的收费。 现在给定时间t (<10000) ，我们必须选择一条从城市0到达城市N-1的路径，使得通行费用最小，并且在给定时间t内完成旅行。
我知道只有一个参数，如只有时间，我们可以使用最短路径算法，如Bellman–Ford algorithm或Dijkstra's algorithm 。 但如何修改它以包含两个约束？ 我们如何为这个问题制定动态规划解决方案？
我试图用DP +完整搜索来解决它。 我在正确的方向，还是有比这些方法更好的算法？
可以使用Dijkstra来解决这个问题，首先你需要创建一个状态图，每个状态代表剩下的城市和时间 。 因此，在每个州（城市A，时间t）和州（城市B，时间t1）之间，如果您可以从城市A移动到城市B并且给定时间为（t1 - t），则只能有一个边。 而每个边缘的价值将是收费。 用标准Dijkstra解决这个问题很简单。
链接地址: http://www.djcxy.com/p/35231.html