In what time can an augmenting path be found?
O(|E| log |V|)
O(|E|)
O(|E|·|V|^2)
O(|E|·|V|^2 log |V|)
Correct Answer: B — O(|E|)
Explanation:
An augmenting path can be found in O(|E|) time by an unweighted shortest path algorithm.
