algorithmcomplexity-theory

Advantage of using Dinic's O((V^2)E) algorithm over Edmond-Karp algorithm O(V(E^2))


Is there any advantage of using Dinic's O((V^2)E) algorithm over Edmond-Karp algorithm O(V(E^2))? In other words, I want to know how is O((V^2)E) better than O(V(E^2)) if it is from a Competitive Programming point of view.


Solution

  • Let's say the total number of vertices is n. The number of edges in a directed connected graph will always be between n-1 (the graph, if undirected, would be a tree) and n(n-1) = n² - n (the graph is complete), so this will be the case for every graph that doesn't have unreachable vertices, and for max flow problems, you'll only analyse the vertices that are reachable from the fountain anyways.

    Mostly the input graphs are not very sparse, so the number of edges in maximum percentage of the cases would be greater than n (might be O(n log n), or in the worst case, O(n^2)).

    So, if you consider the worst case scenario, O(V^2*E) is O(n^4), whereas O(V*E^2) is O(n^5). Hence you see the advantage of using an O(V^2*E) time algorithm over O(V*E^2).