我应该使用什么算法来查找有向下限但没有上限的有向图上的最小流量？

Question

我应该使用什么算法来查找有向下限但不是上限的有向图上的最小流量？比如这个简单的例子:

在文献中,这是最小的成本流问题.然而,在我的情况下,成本与每个边缘所需流量的非零下限相同,所以我在上面提出问题.在文献中,问题是:找到单源/单宿有向无环图的最小成本流的最佳算法是什么,其中每个边具有无限容量,流上的非零下界,以及成本等于流量的下限.

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

我的意思是,如果所有的成本和下限都是1,如上所述...我们正在寻找一个涵盖所有边缘的流程,遵守流程规则,并且不会在从s到t的任何路径上推动太多流量.这只是感觉它不应该要求LP求解器,事实上维基百科关于最小成本流的文章指出"如果容量约束被移除,问题就会减少到最短路径问题"但我认为他们正在讨论下限全部为零的情况.

还有开源C/C++代码,可以在任何地方实现最低成本流量吗？从谷歌搜索可用的东西,我发现我可以自己设置问题作为LP问题,并用开源LP解算器解决,或者我可以使用LEMON,它为最低成本流提供了几种算法.据我所知,boost图库不包含实现.

还有别的事吗？

Answer 1

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

1. 找到一个可行的流程,即满足流量规则和流量下限但不一定是最小流量的流量.这可以通过对图形进行深度优先遍历,在我们遍历时跟踪当前路径,以及在访问先前发现的节点或t,目标节点时,以最大值更低的方式增加当前路径上的流量来实现. - 当前路径上未满足的边缘一直到t.

2. 通过解决最大流量问题将可行流量转换为最小流量.您需要在图表上找到容量等于流量(e)的最大流量 - 下限(e),其中流量(e)表示来自可行流量的流量.从可行流量中减去的最大流量将是最小流量.

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