我要解决的问题如下:
给定一个有向图，找到“覆盖”整个图的最少路径数。多条路径可能经过同一个顶点，但路径的并集应该是所有路径。
对于给定的示例图(见图)，结果应为 2(1->2->4，并且 1->2->3 就足够了)。
通过拆分顶点并为连接入顶点和出顶点的每条边分配下界 1，并将源链接到每个入顶点，将每个出顶点链接到汇(它们不是如图所示，因为它会使整个事情变得困惑)，现在的问题是在具有下限约束的情况下找到图中的最小流。
但是，我读到为了解决这个问题，我必须找到一个可行的流程，然后按如下方式分配容量:C(e) = F(e) - L(e)。但是，通过为每个 Source-vertex 边、vertex-Sink 边和 In-Out 边分配 1 的流，可行流是正确的，总流等于顶点数。但是通过分配新容量，输入输出边(标记为蓝色)的容量为 0(它们的下限为 1，在我们选择可行流时，它们的流为 1)，并且没有流动是可能的。
图。 2:我如何选择“可行流程”
但是，从图中可以明显看出，您可以引导满足每个“顶点边”下限的 2-flow。
我对最小流算法的理解有误吗？哪里错了？!
最佳答案
获得可行流量后，您需要开始“修剪”它，方法是将流量从汇点返回到源头，并遵守下限和容量限制(实际上只是剩余容量)。下面的两个黑色边缘用于向前方向，因为它们还没有流动。涉及源和汇的边被反向使用，因为我们正在撤消它们上已经存在的流。如果您开始从剩余容量的角度考虑所有这些，就会更有意义。
关于algorithm - 具有下限的网络中的最小流量 - 我做错了什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29267096/