我正在寻找一种算法，以在无向加权完整图中给定最大成本的情况下找到具有最小成本和最大长度的两个节点之间的路径。权重非负。
就我现在而言，我正在使用 DFS，而且它非常慢（节点数量较多，长度也最大）。我已经在 DFS 的每次迭代中丢弃了所有不可能的节点。
有人可以向我指出一个已知的算法来更好地处理这个问题吗？
澄清一下：理想情况下，算法应该搜索最小成本的路径，但如果这意味着访问更多节点，则允许增加成本。当它得出结论不可能在不超过成本限制的情况下到达超过 n 个节点并且不可能以更少的成本到达 n 个节点时，它应该结束。
Update
图表示例。我们必须从 A 到 B。成本限制设置为 5：
This path (in red) is ok, but the algorithm should continue searching for better solutions
这是更好的，因为虽然成本增加到 4，但它多包含 1 个节点
这里的路径包含 3 个节点，因此比以前好很多，并且成本是可以接受的 5
最后这个解决方案甚至更好，因为路径也包含 3 个节点，但成本为 4，比以前少。
希望图片比文字更好地解释
Idea 1:
在我看来你的问题是一个变体帕累托最优 http://en.wikipedia.org/wiki/Pareto_efficiency最短路径搜索问题。因为您引用了 2 个不同的最优性指标：
当然，一些附带约束只会使问题更容易计算。
您必须实施多标准 dijkstra 以获得帕累托最优结果。我发现了两篇有前途的英文论文来解决这个问题：
不幸的是，我无法找到这些论文的 pdf 文件以及我之前读过的德语论文:( 尽管如此，这应该是您的切入点，并将引导您找到一种算法来很好、顺利地解决您的问题。
Idea 2:
解决这个问题的另一种方法可能在于计算汉密尔顿路径 http://mathworld.wolfram.com/HamiltonianPath.html，因为完整图中最长的路径确实是哈密尔顿路径。计算完所有此类路径后，您仍然必须找到总边权重成本最小的路径。如果路径长度在任何情况下都比成本更相关，则此场景很有用。
Idea 3:
如果边的成本是更重要的事实，您应该计算给定最大长度的这两个节点之间的所有路径，并搜索具有最常用边的路径。
结论：
我认为使用想法 1 会获得最好的结果。但我不太了解你的场景，因此其他想法可能是选项二。
