What is the Edmonds-Karp algorithm primarily used for?
A
Finding shortest paths B
Computing minimum spanning trees C
Finding maximum flow D
Detecting cycles
Analysis & Theory
Edmonds-Karp is an implementation of Ford-Fulkerson to compute maximum flow.
Which method does Edmonds-Karp use to find augmenting paths?
A
Depth-First Search B
Breadth-First Search C
Dijkstra's Algorithm D
Bellman-Ford Algorithm
Analysis & Theory
Edmonds-Karp always uses BFS to find the shortest augmenting path (fewest edges).
What is the time complexity of the Edmonds-Karp algorithm?
A
O(VE) B
O(V^2) C
O(VE^2) D
O(E log V)
Analysis & Theory
The time complexity is O(V × E^2).
What is updated after each augmenting path is processed?
A
The capacity graph is reset B
The residual capacities of edges C
The adjacency matrix is rebuilt D
The flow is discarded
Analysis & Theory
Residual capacities are updated to reflect the new flows.
Compared to the basic Ford-Fulkerson algorithm, Edmonds-Karp has which improvement?
A
Lower space complexity B
Always terminates in polynomial time C
Handles negative capacities D
Works only on undirected graphs
Analysis & Theory
Because BFS finds shortest augmenting paths, it guarantees polynomial termination.
In Edmonds-Karp, what does the BFS search compute?
A
The path with maximum residual capacity B
The path with minimum cost C
The augmenting path with the fewest edges D
The path with the fewest vertices
Analysis & Theory
BFS finds the augmenting path with the fewest edges.
When does Edmonds-Karp terminate?
A
When no more augmenting paths exist B
When all capacities are doubled C
After V iterations D
After all edges are reversed
Analysis & Theory
It stops when no augmenting path from source to sink remains.
What is the initial flow assigned to all edges before running Edmonds-Karp?
A
Zero B
Equal to capacities C
Random values D
Infinity
Analysis & Theory
All flows start at zero.
Which of the following statements is TRUE about Edmonds-Karp?
A
It works with graphs containing negative capacities B
It improves Ford-Fulkerson by using BFS for augmenting paths C
It only applies to undirected graphs D
It requires edge capacities to be sorted
Analysis & Theory
Its key improvement is BFS for finding augmenting paths.
What theorem does Edmonds-Karp constructively prove?
A
Max-Flow Min-Cut Theorem B
Hall's Marriage Theorem C
Menger's Theorem D
Dilworth's Theorem
Analysis & Theory
It shows maximum flow equals the capacity of the minimum cut.