Maximum flow in undirected graph with non-integer weights

Question

If I would want to find maximum flow in undirected graph, how could I do this?

On Wikipedia page http://en.wikipedia.org/wiki/Maximum_flow_problem it says that algorithms require directed graphs (I would just convert each edge to a pair of edges) but the problem is that I may have non integer weights (for example 0.5).

Is there any existing algorithm that is suitable for this problem?

Answer 1

the stoer-wagner algorithm does the job. it dwells on the duality of max-flow/min-cut. an algorithm in the vein of the seminal ford-fulkerson (which fails on real-valued edge weights) would be edmonds-karp.