Question

What is the running time of Dinic’s blocking flow algorithm?

(a) O(V^2E)

(b) O(VE^2)

(c) O(V^3)

(d) O(E max |f|)

The question was asked in a national level competition.

The query is from Flow Networks in division Flow Networks of Data Structures & Algorithms II

Answer 1

The correct option is (a) O(V^2E)

For explanation: The running time of Dinic’s blocking flow algorithm is O(V^2E). The running of Ford-Fulkerson algorithm is O(E max |f|).