Search code examples
algorithmtime-complexitymax-flowford-fulkerson

Why is ford-fulkerson so ubiquitous?


When looking at max flow solutions, ford-fulkerson seems to be ubiquitous in that it is the algorithm most people implement to solve this problem. However there are many more algorithms that can solve the problems and at a significantly better time complexity. So why is ford-fulkerson still so widely used then?


Solution

  • Ford–Fulkerson is the simplest algorithm that embodies the key idea that a flow is maximum if and only if it has no augmenting path. This makes it useful for teaching.

    Since F–F doesn't specify how to find an augmenting path, it's more of a framework than an algorithm. Edmonds–Karp is an instantiation of F–F that bounds the number of augmenting paths that must be found. Dinic's algorithm improves on Edmonds–Karp by keeping a data structure that allows it to find augmenting paths more efficiently. (Off the beaten path a bit, the O(n log n)-time algorithm for s-t flow in planar networks due to Borradaile and Klein is also an F–F instantiation.)

    The push-relabel algorithms take the idea behind Dinic's algorithm one step further, but they break out of the F–F mold in using preflows, not flows (preflows allow more flow to enter a vertex than leaves, but not vice versa). Historically they followed Dinic's algorithm and make more intuitive sense as a reaction to Dinic.

    The other algorithms on that list are complicated and not suitable for undergraduate instruction, which explains the lack of tutorial material.