CODEWITHSUNDEEP
algorithmgraph
Herokiller
Herokiller

Reputation: 2991

estimate the flow in the graph

Given undirected graph, all edges have weight 1; N, M are about 10^6 I need to find whether the flow between source and sink is bigger than some value X. X is quite small.

Using bfs until the flow is equal to X gives O(M*X) this is too slow for me.

Is there any quicker method to estimate flow?

Upvotes: 6

Views: 346

Answers (1)

iloahz
iloahz

Reputation: 4561

what you need is basically maxflow, see http://en.wikipedia.org/wiki/Maximum_flow_problem

and Dinic's algorithm is recommended for practical efficient.

and in case you need some example, you may refer to one of my code, at http://wiki.attiix.com/index.php?title=Maxflow

Upvotes: 1

Related Questions