The algorithm has {{nowrap|''O''(''V''^2{{sqrt|''E''}})}} time complexity.
==Sample implementationimplementations==
[[C (programming language)|C]] implementation:
<source lang="c">
Line 318:
return sum(F[source])
</source>
Note that the above implementation is not very efficient. It is slower than [[Edmonds–Karp algorithm]] even for very dense graphs. To speed it up, you can do at least two things:
# Make neighbour lists for each node, and let the index <code>seen[u]</code> be an iterator over this, instead of the range <math>0,\ldots,n-1</math>.
# Use a '''gap heuristic'''. If there is a <math>k</math> such that for no node, <math>\mathrm{height}(u)=k</math>, you can set <math>\mathrm{height}(u)=\max(\mathrm{height}(u), \mathrm{height}(s) + 1)</math> for all nodes except <math>s</math> for which <math>\mathrm{height}(u)>k</math>. This is because any such <math>k</math> represents a [[max-flow min-cut theorem|minimal cut]] in the graph, and no more flow will go from the nodes <math>S = \{u\mid \mathrm{height}(u)>k\}</math> to the nodes <math>T = \{v\mid \mathrm{height}(v)<k\}</math>. If <math>(S,T)</math> was not a minimal cut, there would be an edge <math>(u,v)</math> such that <math>u \in S</math>, <math>v \in T</math> and <math>c(u,v)-f(u,v) > 0</math>. But then <math>\mathrm{height}(u)</math> would never be set higher than <math>\mathrm{height}(v)+1</math>, contradicting that <math>\mathrm{height}(u) > k</math> and <math>\mathrm{height}(v) < k</math>.
