algorithm - 沿循环的最大流量

Question

我有一个有向图，我想找到我可以沿着循环(循环)发送的最大流量。标准的 Ford-Fulkerson 方法可以使用增加路径(在本例中为循环)，还是我需要一些特殊的东西？没有源/汇，我只想按周期发送流。

我想要最大化的数量是 Sum(f(i,j))，其中 f(i,j) 是沿着该边的流量，在所有边上，在常规最大值下。流约束(每条边都有一个非负的有限容量，并且每个顶点的流入(v)=流出(v))。

Answer 1

你需要做一些比扩充更复杂的事情。问题是，一旦你沿着一个循环发送流，你就可以插入或不插入向后的剩余弧。如果你这样做了，那么就没有什么可以阻止你将流直接发送回它的来源。如果你不这样做，那么你可以增加错误的循环。例如在图中

c-->d
^   |
|   v
b-->e
^   |
|   v
a<--f

如果所有弧都有单位容量，您可能会增加 a->b->e->f->a 并错过较长的循环 a->b->c-> d->e->f->a.

相反，您需要做的是运行 Bellman--Ford(或其他一些容忍负长度的最短路径算法)来找到一个前向弧多于后向弧的循环并使其饱和。 (如果不存在这样的循环，那么你有一个最优解。)然后你得到一个 O(OPT poly(n)) 边界，就像在 Ford--Fulkerson 中一样，其中所有弧都具有整数容量并且 OPT 是最优目标值。你可以搜查circulation problems上的文献/用于优化的网络单纯形。

检测前向弧多于后向的循环:设置每个前向弧的长度为-1，每个后向弧的长度为1。将每个顶点的距离标签初始化为0(模拟人工效果)没有传入弧和到其他顶点的长度为 0 弧的源)。运行Bellman--Ford，判断是否存在负长周期。