假设我有一个加权图，其中权重代表距离(以英里为单位)。我要找到从某个顶点 S 到某个顶点 T 的最短路径。此外，假设每个顶点都有相关的货币成本。现在，一开始我有 $M(即 M 美元)。我的工作是找到不产生任何债务的最短路径。
我的尝试:
我使用 Dijkstra 算法，但我的解决方案仅在某些情况下有效，并非在所有情况下都有效。有谁知道如何解决这个问题，所以它可以工作——请不要使用 SIMPLEX，除非你完全实现它。非常感谢 java 工作代码。我已经查看了 top-coders 上的 Upper-Intermediate 示例但我不知道如何实现他们的伪代码。
我尝试了许多不同的代码/方法，但它们都有太多错误。我的尝试太多了，无法发布，只发布一个没有多大意义。
最佳答案
你说得对，Dijkstra 算法只在某些情况下有效，因为它只选择成本较低的边，而你必须验证两个条件的存在:
- 路径的总成本(美元)在
M美元的预算范围内； - 里程数最少。
这是一种保证正确但运行起来可能真的很慢的方法。你做了两个步骤:
- 根据美元成本找到所有可能的路径，并将它们放入数组或列表中；
- 为每条路径计算英里数并选择路径或具有最小英里数的路径。
这种方法的问题是生成的列表可能非常大。所以也许有更好的方法来解决这个问题。
关于java - 除了必须计算的值之外还有一个附加条件的动态规划问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10593595/