# Max flow algorithm for floating-point weights and E~=10*V

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. O(V^3) algorithms take too much time, but O(E^2) algorithms are much more preferable. More specifically, you can assume V~=1M and E~=10M where M stands for millions.

Orlin's algorithm can solve max flow in sparse graphs in $$O(|V| |E|)$$ time. See
• Orlin's algorithm seems more like a theoretical curiosity than a practical algorithm. Sleator & Tarjan's implementation of Dinic's algorithm works in $O(|V| |E| \log |V|)$ time and was published in 1982. – Laakeri Dec 26 '19 at 23:49