Menu
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?
416
Flow or rooted graph (graph theory), a graph in which a vertex has been distinguished as the root. Control-flow graph (computer science), a representation of paths through a program during its execution. Flow graph (mathematics), a directed graph linked to a set of linear algebraic or differential equations.
The max-flow min-cut theorem states that the maximum flow through any network from a given source to a given sink is exactly equal to the minimum sum of a cut. This theorem can be verified using the Ford-Fulkerson algorithm. This algorithm finds the maximum flow of a network or graph.
The value of a flow is the sum of the flow on all edges leaving the source s. We later show that this is equivalent to the sum of all the flow going into the sink t.
What is a Network Flow? A network flow is a series of communications between two endpoints that are bounded by the opening and closing of the session. There is a lot of data in a flow. Most routers offer the capability of collecting these flows for analysis.
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
178
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
