graph - 具有非整数权重的无向图中的最大流

Question

如果我想在无向图中找到最大流量，我该怎么做？

在维基百科页面http://en.wikipedia.org/wiki/Maximum_flow_problem它说算法需要有向图（我只是将每条边转换为一对边）但问题是我可能有非整数权重（例如0.5)。

有没有适合这个问题的现有算法？

Answer 1

stoer-wagner 算法完成了这项工作。它专注于最大流量/最小切割的对偶性。具有开创性的ford-fulkerson的算法（在实值边缘权重上失败）将是edmonds-karp。