algorithm - 具有两个不同边权重的图

Question

我正在尝试找到两点之间的路径。我图中的每条边都有两个单独的权重。如果您只考虑两点之间的第一个权重，我已经知道最短路径。我需要做的是最大化第二个权重，同时确保第一个不超过约束。约束是第一个权重的总和不应超过它在最短路径上的总和超过 X%。我该怎么做呢？最终的解决方案不必是精确的解决方案，因为它旨在成为一种启发式方法。

在某些情况下(但不是全部)，该图的边从节点 1 到节点 2，从节点 2 到节点 1。

请注意

BFS 会花费太多时间。我的问题是我需要走一条不超过第一个重量总和限制的路径，但第二个重量的总重量需要最大化。该图非常庞大，有数十万条边。

Answer 1

我会简单地进行广度优先搜索:

从您的起始节点开始，收集所有可能的下一个节点并跟踪第一个和第二个权重，只要第一个权重满足约束。

从这些节点构建所有可能路径的列表并迭代。

如果一个节点不再产生任何候选路径，因为所有边的第一个权重都太高，则将其与当前最佳路径进行比较，如果新路径更好，则将其替换为新路径。