Guest
|
 Posted: Sun Oct 05, 2008 1:17 pm Post subject: Improving Ford Fulkerson Edmonds Karp maximum flow computing |
 |
|
The meet in middle method for maximum flow calculation
Give the problem to compute the maximum flow between a source and a
destination in a graph, one could use the Ford Fulkerson method with
Edmonds and Karp breadth-first-scanning in O(VE^2). Imagining that we
are computing the flow between 2 cities in the world, say Bucharest
and Bruxelles, the shortest ways are added first to the flow, then a
storm of long ways arise even overseas through America or Asia, that
contribute to the maximum flow.
It>s rather inefficient to compute the flow this way at a global
scale, instead, think of extending ways in the same time from the
source to the destination and from the destination to the source and
when the ways meet in middle we>ve found an augmenting path (an
ameliorating way), then the process continues in the current step with
all the ways that meet somewhere "in the middle". After the first full
step, when there are no more ways to link paths into gains, another
step is required on the modified graph after augmenting till no gains
are available in a step. At this point we>ve found the maximum flow.
So instead of going one way at a time, we do one move expanding the
source (towards the destination) and another move expanding the
destination (towards the source). When the 2 ways meet in middle,
we>ve found an amelioration and we use it. One step of the algorithm
stops when there are no more gains joining paths. When this happens,
another full step is required and when there>s not even the slightest
gain in one step, the algorithm finishes and the maximum flow is
found.
Think as all the cars leaving from Bruxelles to Bucharest and vice
versa chaotic in the same time and when they meet somewhere "in the
middle" (but also could be overseas), they return to where they came
from with some gain.
The number of full steps required to find the maximum flow in a graph,
depends on the graph, an average of 2-3 full steps required it>s
observed, but there are also cases when that number increases.
Determining by formula what>s the average number of big steps or the
overall complexity of the algorithm is a bit strange, but it is
obviously better than standard one way at a time Ford Fulkerson -
Edmonds Karp algorithm.
Hope you find this post useful.
Badita Robert - Romania |
|
