But, of course, the aliens aren't just going to give up that missile. They do have to transport it from their base to their launch platform, before they can launch it.
Their base is heavily defended with energy shields and plasma cannons, and so is the launching platform.
So we, as intelligent human beings, have figured out that we need to bomb some roads in between the base and the platform so the aliens can't transport their missile. Now this might sound easy, but there are a whole bunch of roads with varying size that can be used by the aliens.
Now we are a little low on funds and resources, so we want to separate base from platform in the cheapest way.
So, the only way to effectively solve this problem is by using a maximum flow / minimum cut algorithm. The maximum flow of an undirected graph is calculated by continuously trying to find a path from source, the alien base, to sink, the launch platform, and selecting the edge with the smallest capacity in that path.
After that we substract the capacity of that edge of the capacity of all other edges in the path, creating a residual capacity graph, and we also add it to the graphs maximum flow.
We continue to use this technique until there is no path from source to sink.
Now we have a few edges that are used at maximum capacity, as their residual capacity will be 0.
One might already see that if those edges are removed from the graph, the source and sink will be in 2 different partitions.
The only thing is that when doing that, we might remove to much.
The best way is to do one last breadth-first search to see which edges start from a vertex reachable from the source, but end in a vertex that's not reachable from the source (this will be an edge with a residual capacity of 0).
When removing these edges we will have found the cheapest way to separate source from sink.
Want to know more about this problem, and my implementation? Comment on this post, and I might just give the subject some extra attention.
Published with Blogger-droid v1.6.5
