尽可能快地在图中找到任何可行的流
Finding any feasible flow in graph as fast as possible
我有一个带有下限和上限的流程图，我的任务是尽快找到任何可行的解决方案。我发现了许多 maximum/minimum 流程的算法和方法等等（也很多时候使用可行的解决方案作为起点）但没有任何可行解决方案的具体内容。有没有什么algorithm/approach专门针对它又快的？
所以我终于有时间总结一下了。我使用的解决方案是采用初始图形并在这些步骤中对其进行转换。
（权重顺序为：下限、当前流量、上限。）
1.通过 (0, 0, infinity) 的边将 t 连接到 s。
2。到每个节点
初始图添加余额值等于：（下限的总和
入边 - 出边下界的总和）。
3。设置上层
每条边的边界到（上限 - 下限）。设置下限
并且每条边的电流为 0.
4.现在创建新的 s (s') 和新的 t (t')，这将是我们新的开始和结束（不要删除图中已经存在的 s 和 t，它们只是变成了
正常节点）。
5.创建从 s' 到每个具有正平衡的顶点的边 (0,
0, vertex.balance) 范围。
6.用 (0,
0, abs(vertex.balance)).
7. 运行 Ford-Fulkerson（或您选择的其他最大流量算法）
在新图表上。
8.对于初始图和值的每条边
边缘与转换前的初始旧下界，你有你的
初始图的每条边的初始流。
这个问题实际上比在提供可行流量的情况下最大化流量要难一些。
我有一个带有下限和上限的流程图，我的任务是尽快找到任何可行的解决方案。我发现了许多 maximum/minimum 流程的算法和方法等等（也很多时候使用可行的解决方案作为起点）但没有任何可行解决方案的具体内容。有没有什么algorithm/approach专门针对它又快的？
所以我终于有时间总结一下了。我使用的解决方案是采用初始图形并在这些步骤中对其进行转换。
（权重顺序为：下限、当前流量、上限。）
1.通过 (0, 0, infinity) 的边将 t 连接到 s。
2。到每个节点 初始图添加余额值等于：（下限的总和 入边 - 出边下界的总和）。
3。设置上层 每条边的边界到（上限 - 下限）。设置下限 并且每条边的电流为 0.
4.现在创建新的 s (s') 和新的 t (t')，这将是我们新的开始和结束（不要删除图中已经存在的 s 和 t，它们只是变成了 正常节点）。
5.创建从 s' 到每个具有正平衡的顶点的边 (0, 0, vertex.balance) 范围。
6.用 (0, 0, abs(vertex.balance)).
7. 运行 Ford-Fulkerson（或您选择的其他最大流量算法） 在新图表上。
8.对于初始图和值的每条边 边缘与转换前的初始旧下界，你有你的 初始图的每条边的初始流。
这个问题实际上比在提供可行流量的情况下最大化流量要难一些。