# 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

Max flows in O(nm) time, or better. James B. Orlin. STOC 2013.

You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex. I don't know whether the algorithm is better in practice.

Perhaps someone else will have better suggestions for you.

• 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. Dec 26 '19 at 23:49