我应该使用什么算法来在有流量下限但没有上限的有向图中找到最小流量?例如这个简单的例子:
从我的研究来看,人们处理任何类型网络的最小费用的主要方法是将问题设置为LP类型问题并以这种方式解决。然而,我的直觉是,没有流量上限,即具有无限容量的边使问题变得更容易,因此我想知道是否有一种专门针对这种情况使用更多“图形”技术比单纯法等的算法。
我是说,如果所有成本和下限都像上面一样为1...那么我们正在寻找一种涵盖所有边缘的流,遵守流规则,并且没有将太多的流量通过从s到t的任何路径。对我来说,这似乎不需要LP求解器,事实上,维基百科关于最小成本流的文章指出:“如果容量约束被移除,则问题将简化为最短路径问题”,但我认为他们谈论的是所有下限都为零的情况。
此外,是否有开源的C/C++代码用于最小成本流?通过搜索可用内容,我发现我可以将问题设置为自己的LP问题并使用开源LP求解器进行求解,或者我可以使用LEMON,该软件提供了几种用于最小成本流的算法。据我所知,boost图书馆不包括实现。
还有其他需要注意的吗?