Graph Theory37 sections · 1633 units
Open in CourseQuiz: Edmonds-Karp Complexity
Knowledge check
Check Your Understanding
Edmonds-Karp uses BFS to find augmenting paths. Why does BFS guarantee time instead of the potentially unbounded Ford-Fulkerson?
- A.BFS always finds the path with maximum bottleneck capacity
- B.BFS finds shortest augmenting paths, and shortest-path distances never decrease, bounding iterations to
- C.BFS visits fewer nodes than DFS in residual graphs
- D.BFS prevents cycles in the augmenting path