CODEWITHSUNDEEP
algorithmtime-complexitymax-flowford-fulkerson
user13925866
user13925866

Reputation:

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?

Upvotes: 1

Views: 654

Answers (2)

Vishal Sharma
Vishal Sharma

Reputation: 19

Ford-Fulkerson algorithm gives the fundamental paradigm to solve a maximum flow problem. Suppose a graph, consisting of Vs and Es, has a source and sink defined. Along with this there is a capacity defined for each E. The ford fulkerson algorithm directs us to find an augmenting path (a path whose capacity has not reached its limit), and to send as much flow as we can through that path, and accordingly update the capacities.

Ford-Fulkerson algorithm however, doesn't exactly specify how to find these augmenting paths. This is the primary research that is done today in this field. The classic ford fulkerson with simple graph searching algorithms give the time complexity of O(n^2). There have been several attempts from Dinitz, to many other CS experts such as Spielman and Teng, who have managed to bring the complexity down to a level of O(n^1.43). The primary challenge these days is to bring the time to nearly linear.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65427

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.

Upvotes: 3

Related Questions