Question

In what time can an augmented path be found?

(a) O(|E| log |V|)

(b) O(|E|)

(c) O(|E|^2)

(d) O(|E|^2 log |V|)

The question was posed to me during an interview.

The origin of the question is Flow Networks in chapter Flow Networks of Data Structures & Algorithms II

Answer 1

Right choice is (b) O(|E|)

The explanation is: An augmenting path can be found in O(|E|) mathematically by an unweighted shortest path algorithm.