python - 尽可能快地在图中找到任何可行的流

Question

我有一个带有下限和上限的流程图，我的任务是尽快找到任何可行的解决方案。我发现了许多算法和最大/最小流量等方法（也多次使用可行解决方案作为起点），但对于任何可行解决方案都没有具体说明。是否有任何特定于它且快速的算法/方法？

Answer 1

所以我终于有时间总结一下了。我使用的解决方案是获取初始图并在这些步骤中对其进行转换。

（权重按以下顺序排列：下限、电流、上限。）

1. 通过 (0, 0, infinity) 的边缘将 t 连接到 s。

2. 对初始图的每个节点添加平衡值等于：（传入边的下界之和 - 传出边的下界之和）。

3. 将每条边的上限设置为（上限 - 下限）。将每条边的下限和电流设置为 0。

4. 现在新建 s (s') 和 new t (t') 这将是我们新的开始和结束（不要删除图中已经存在的 s 和 t，它们只是成为普通节点）。

5. 创建从 s' 到具有 (0, 0, vertex.balance) 边界的正平衡的每个顶点的边。

6. 用 (0, 0, abs(vertex.balance)) 从每个具有负平衡的顶点到 t' 创建边。

7. 在新图上运行 Ford-Fulkerson（或您选择的其他最大流量算法）。

8. 对于初始图的每条边，在转换前具有初始旧下限的边的总和值，并且您有初始图的每条边的初始流。

这个问题实际上比在提供可行流量时最大化流量要难一些。