[tubbzor]

You are very correct. Max-flow/min-cut reduces to tons of other problems where this algorithm will be optimized.

Here's a nice little introduction I found with some reductions on the first couple slides: http://www.cs.princeton.edu/courses/archive/spr04/cos226/lec...

I just finished my algorithms undergrad class last semester; one of the questions on the final was 'you are a terrorist looking to cut off supplies to your enemy, which 3 nodes must you destroy to cut off the supply network?' And there was a complicated graph with probably 10 nodes and twice as many edges (very difficult to brute force in the allotted time), and we had to find the min-cut which would severe the flow. Some really cool problems reduce to max-flow.

[mcintyre1994]

Our lecturer told us that the problem was initially considered simultaneously by Russians trying to optimise the rail transport of stuff from USSR back to Russia and Americans trying to work out the cheapest way to destroy that network. Not sure if it's true, but it helps me think about the problem a lot.

Edit: I clicked the link, he used them exact slides. That set of slides comes up a lot, they're great.

[tubbzor]

You are right! Edmonds-karp was developed (really just a modified Ford-Faulkerson approach with a BFS as opposed to a random augmenting path...but we'll give it to him), yielding an O(ve^2) algorithm. A russian (soviet) mathematician named Dinic nearly simultaneously, and independently, developed an O(ev^2) algorithm which we can see beats Edmonds-karp as edge density grows.