约束的最大容量路径问题

Question

我试图开发一种有关限制的最大容量问题的算法，但无法弄清楚正确输出所需的必要更改。 问题是：

具有两个参数的无向图（重量，成本）。我们需要找到最大容量路径问题从源到目的地，使路径的成本（路径边缘的和）在用户指定的固定值内。换句话说，它（沿着路径的成本参数的总和）是由恒定值的上限。

我通过添加和额外的成本约束来修改现有算法，同时放松边缘但无法为所有类型的图表制作它。我也想知道这个问题是否完整。

Answer 1

可以在多项式时间中解决。例如，您可以使用重量的二进制搜索。鉴于候选权重，删除重量较低的所有边，然后找到最低成本路径并测试其成本是否低于下限;这告诉你重量是否太高或太低。重复直到二进制搜索收敛。