假设我有一个加权图，其中权重表示距离（以英里为单位）。我要找到从某个顶点 S 到某个顶点 T 的最短路径。此外，假设每个顶点都有货币成本。现在，一开始我有$M（即 M 美元）。我的工作是在不产生任何债务的情况下找到最短的路径。
我的尝试：
我使用 Dijkstra 的算法，但我的解决方案仅适用于某些实例，但不是全部。有谁知道如何解决这个问题，所以它工作 - 请不要使用SIMPLEX，除非你完全实现它。非常感谢Java工作代码。我已经看过顶级编码器的Upper-Intermediate示例，但我不知道如何实现他们的伪代码。
我尝试了许多不同的代码/方法，但它们都有太多的错误。我的尝试太多了，无法发布，只发布一个没有多大意义。
你说Dijkstra的算法只在某些情况下有效，因为它只选择成本较低的边缘，而你必须验证两个条件的存在：
- 路径的总成本（以美元为单位）在
M美元的 bugdet 范围内; - 英里数是最小的。
一种保证正确但运行速度可能非常慢的方法就是这样。您需要执行两个步骤：
- 以美元为单位找到所有可能的成本路径，并将它们放入数组或列表中;
- 对于每条路径，计算英里数并选择具有最小英里数的路径。
这种方法的问题在于生成的列表可能非常大。所以也许有更好的方法来解决这个问题。