For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE).
On the other hand, the algorithms I most commonly see implemented are (I don't claim to have done an exhaustive search; this is just from casual observation):
- Edmonds-Karp: $O(VE^2)$,
- Push-relabel: $O(V^2 E)$ or $O(V^3)$ using FIFO vertex selection,
- Dinic's Algorithm: $O(V^2 E)$.
Are the algorithms with better asymptotic running time just not practical for the problem sizes in the real world? Also, I see "Dynamic Trees" are involved in quite a few algorithms; are these ever used in practice?
Note: this question was originally asked on stack overflow, here, but I was told it would be a better fit here.
EDIT: I asked a related question on cs.stackexchange, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.