我正在寻找一种算法，以在无向加权完整图中给出最大成本的最小成本和最大长度来找到两个节点之间的路径 . 重量是非负的 .
我现在站在那里，我正在使用DFS，它很慢（节点数量和最大长度） . 我已经在DFS的每次迭代中丢弃了所有不可能的节点 .
有人能指出我已知的算法来更好地处理这个问题吗？
为了澄清：理想情况下，算法应搜索最低成本的路径，但如果这意味着访问更多节点，则允许增加成本 . 它应该在它得出结论认为在不超过成本限制的情况下达不到n个节点并且不可能以更低的成本到达n个节点时结束 .
Update
图表示例 . 我们必须从A到B.成本限制设置为5：
此路径（红色）没问题，但算法应继续搜索更好的解决方案
这样做更好，因为虽然成本增加到4，但它还包含1个节点
这里的路径包含3个节点，因此它比以前好很多，成本是可接受的5
最后这个解决方案甚至更好，因为路径还包含3个节点，但成本为4，比以前少 .
希望图像解释比文本更好
1 回答
Idea 1:
在我看来，你的问题是pareto optimal最短路径搜索问题的变体 . 因为您参考了2个不同的最优度指标：
边缘计数的最长路径
边缘权重最短路径
当然，一些侧面约束只会使问题更容易计算 .
您必须实现多标准dijkstra才能获得帕累托最优结果 . 我在这个问题上找到了两篇有用的英文论文：
多准则帕累托最优路径算法
关于多准则最短路径问题
不幸的是，我无法找到那些论文的pdf文件以及我在德语之前读过的论文:(不过这应该是你的切入点，并会引导你找到一个算法来很好地解决你的问题 .
Idea 2:
解决这个问题的另一种方法可能在于hamilton path的计算，因为完整图中的最长路径确实是汉密尔顿路径 . 计算完所有这些路径后，您仍然需要找到总边缘权重成本最小的路径 . 如果路径的长度在每种情况下都比成本更相关，则此方案很有用 .
Idea 3:
如果边缘的成本是更重要的事实，则应计算给定最大长度的这两个节点之间的所有路径，并搜索具有最多使用边缘的节点 .
Conclusion:
我认为最好的结果将通过使用想法1获得 . 但我不了解你的情况，因此其他想法可能是一个选项二 .