Loading practice questions
What is the running time of an unweighted shortest path algorithm whose augmenting path is the path with the least number of edges?
Correct Answer: C — O(EV^2)
Explanation:
Each augmenting step takes O(|E|) using an unweighted shortest path algorithm, yielding an O(|E|²|V|) bound on the running time.