c++ - 我应该使用什么算法在流量有下限但没有上限的有向图中找到最小流量？

Question

我应该使用什么算法在有下界但没有上界的有向图上找到最小流？比如这个简单的例子:

在文献中这是一个最小成本流问题。然而，在我的例子中，成本与每条边所需的流量的非零下限相同，所以我用上面的措辞表达了这个问题。在文献中，问题是:找到单源/单汇有向无环图的最小成本流的最佳算法是什么，其中每条边具有无限容量，流的非零下限，以及成本等于流的下限。

根据我的研究，人们处理任何类型网络的任何类型的最低成本的主要方式似乎是将问题设置为 LP-type problem并以这种方式解决。然而，我的直觉是流量没有上限，即具有无限容量的边缘使问题更容易，所以我想知道是否有一种算法专门针对这种情况使用比单纯形法等更多的“图形”技术。阿尔。

我的意思是，如果所有成本和下限都像上面那样为 1...那么我们正在寻找一个覆盖所有边的流，遵守流规则，并且不会通过任何路径插入太多流s 到 t。这只是感觉它不应该需要我的 LP 求解器，事实上维基百科关于最小成本流的文章指出“如果删除容量限制，问题将减少到最短路径问题”，但我认为他们正在谈论下界全为零的情况。

还有开源的 C/C++ 代码可以在任何地方实现最低成本流吗？通过谷歌搜索可用的内容，我发现我可以自己将问题设置为 LP 问题并使用开源 LP 求解器解决，或者我可以使用 LEMON，它提供了几种最小成本流算法。据我所知，boost 图形库不包含实现。

还有什么吗？

Answer 1

在没有上限的情况下，找到图的最小流的最简单方法(最容易实现、理解并且相当有效)如下:

1. 找到可行流，即满足流规则和流下限但不一定是最小流的流。这可以通过对图进行深度优先遍历来实现，在我们遍历时跟踪当前路径，并在访问先前发现的节点或目标节点 t 时，增加当前路径上的流- 将当前路径上不满足边的边界一直到 t。

2. 通过求解最大流问题将可行流转化为最小流。您需要在图上找到容量等于 flow(e) - lower-bound(e) 的最大流，其中 flow(e) 表示来自可行流的流。从可行流量中减去的最大流量将是最小流量。

在图形也有流量上限的情况下，也可以执行上述版本。在那种情况下，第 1 步会更复杂，但可以通过在特殊构造的图上执行初始最大流计算来解决。