CODEWITHSUNDEEP
graphmax-flow
Andna
Andna

Reputation: 6689

Maximum flow in undirected graph with non-integer weights

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?

Upvotes: 0

Views: 1776

Answers (1)

collapsar
collapsar

Reputation: 17238

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.

Upvotes: 1

Related Questions