我正在寻找一种算法，以在给定无向加权完整图中的最大成本的情况下找到具有最小成本和最大长度的两个节点之间的路径。权重是非负的。
就我现在的立场而言，我正在使用 DFS，而且速度非常慢（节点数量多且长度也最大）。我已经在 DFS 的每次迭代中丢弃了所有不可能的节点。
有人可以指出一个已知的算法来更好地处理这个问题吗？
澄清一下：理想情况下，算法应该搜索最小成本的路径，但如果这意味着访问更多节点，则允许增加成本。当它得出结论：在不超过成本限制的情况下不可能到达超过 n 个节点并且不可能以更少的成本到达 n 个节点时，它应该结束。
更新
图表示例。我们必须从 A 到 B。成本限制设置为 5：
这条路径（红色）没问题，但算法应该继续寻找更好的解决方案
这更好，因为虽然成本增加到 4，但它包含了 1 个节点
这里的路径包含 3 个节点，所以它比以前好很多，成本是可以接受的 5
最后，这个解决方案甚至更好，因为路径也包含 3 个节点，但成本为 4，比以前少。
希望图片比文字解释得更好
想法1：
在我看来，您的问题是帕累托最优最短路径搜索问题的变体。因为您参考了 2 个不同的最优性指标：
当然，一些侧面约束只会使问题更容易计算。
您必须实施多标准 dijkstra 以获得帕累托最优结果。对于这个问题，我发现了两篇很有前途的英文论文：
不幸的是，我无法找到这些论文的 pdf 文件以及我之前读过的德语论文 :( 不过，这应该是您的切入点，并将引导您找到一种算法来顺利顺利地解决您的问题。
想法2：
解决这个问题的另一种方法可能在于计算汉密尔顿路径，因为完整图中最长的路径确实是汉密尔顿路径。在计算完所有此类路径后，您仍然必须找到总边权成本最小的路径。如果路径的长度在每种情况下都比成本更相关，则此方案很有用。
想法3：
如果边的成本是更重要的事实，您应该计算给定最大长度的这两个节点之间的所有路径，并搜索使用最多边的路径。
结论：
我认为使用想法 1 将获得最佳结果。但我不太了解您的情况，因此其他想法可能是选项二。
这个问题可以表述为具有优先级的多目标约束满足问题：
这个问题是 NP 难的。因此，对于这个问题没有精确的多项式时间算法。但是一个简单的本地搜索算法可以帮助你：