在这些算法中,哪种算法将是解决最大流问题的最有效算法
最佳答案
解决最大流问题的最佳算法是什么?
答案是:这取决于...
没有关于图表的任何信息,您有:
- Ford–Fulkerson 算法 O(f*E)
- Edmonds–Karp 算法 O(V*E^2)
- Dinic 算法 O(V^2*E) 但在实践中非常快
您必须根据问题的内存和时间限制选择使用哪一个。
V:图中的顶点数
E:图中的边数
f:是图中的最大流
二分图
此外,如果它是一个二分图,您的实现可以是 O(n*m)
n:集合A的基数
m:集合B的基数
竞争性编程:
在竞争性编程中,Dinic 算法 是最有用的算法之一,因为在实践中速度非常快。我解决的许多问题都是使用 Dinic。尽管如果问题的限制不是很强,那么实现Ford–Fulkerson 算法或Edmonds–Karp 算法 比Dinic 算法更快(编码时间也很重要)
关于algorithm - 使用 dincis 算法和 ford fulkerson 解决最大流问题的最佳算法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55419388/