问在有向图上有下界但没有上界的情况下，我应该使用什么算法来求最小流？

EN

在没有上界的情况下，最简单的方法--最简单的实现、理解和合理有效的方法--求图的最小流如下：

1. 寻找一个可行的流，即满足流规则和流的下界但不一定是最小流的流。这可以通过对图进行深度第一次遍历，在我们遍历时跟踪当前路径，并在访问先前发现的节点(目标节点)时，通过当前路径上不满足的边的最大下限来增强当前路径上的流量，直到t。
2. 通过求解最大流问题，将可行流转化为最小流。您需要在具有等于flow(e) -下限(E)的图形上找到最大流，其中flow(e)是指来自可行流的流。从可行流中减去的最大流量将是最小流。

在图也具有流上界的情况下，还可以执行上述版本的操作。在这种情况下，步骤1更复杂，但可以通过在特殊构造的图上执行初始最大流计算来求解。

写一个解决者是不平凡的。

看柠檬库(硬币的一部分-或)。对于最小成本流问题，它有许多优化算法。您可以选择哪种算法对您的数据最有效。

有关柠檬的信息，请参见http://lemon.cs.elte.hu/trac/lemon。

有关最小成本网络流的详细信息，请参阅http://lemon.cs.elte.hu/pub/doc/1.3/a00607.html。

在每条边界上添加所有流的“下界”：无论如何，任何可行的解决方案都需要这样做。

对于每个节点从接收器n的拓扑顺序(即沿边)，如果边沿的和S-大于输出的和S+，则在s和t之间最短路径的所有边缘上添加流S+ - S- (构造最短路径列表，同时提高效率)。

然后，您有一个“最小”的辅助(在每个可行的解决方案中都需要它)，例如S+ - S-在每个节点上都是非负的，并且在每个边上都满足最小容量。

然后，将该问题归结为同一图结构上的多流问题：

• 来源相同；
• 没有容量限制；
• 每一个S+ - S-严格为正的节点都会成为具有所需的流S+ - S-的接收器。
• 如果初始接收器是非负的(否则任何解决方案都会满足初始约束)，那么初始接收器(它有必需的流F)将成为流F - S-的接收器。

编辑:对于您的问题，图表如下所示

     x1 -- x2
   /   \     \
 s      \     t
   \     \   /
     x3 -- x4

对于每个边都有最小的容量1，并且我认为在接收器t上不需要最小的流。

首先给每个边分配一个。

每个节点(当然，s和t除外)的差异是：

x1: 1
x2: 0
x3: 0
x4: -1

唯一的负面因素是x4；我们将1添加到从x4到t的最短路径上的每个边，在这种情况下添加到边缘(x4, t)。

现在，S+ - S-对于每个节点都是非负的，并且只对x1是正的；这个问题归结为一个多流问题(在这种情况下，它是一个简单的流问题)，其中请求的流在x1是1，而源仍然是s。