E is the number of edges in the graph and f is maximum flow in the graph. When…
2018
E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulberson algorithm is bounded by :
- A.
O (E∗f)
- B.
O (E2∗f)
- C.
O (E∗f 2 )
- D.
O (E2∗f 2 )
Attempted by 48 students.
Show answer & explanation
Correct answer: A
Answer: O (E * f)
Explanation: Key ideas:
With integer capacities, every augmentation increases the total flow by at least 1, so the number of augmentations is at most f (the value of the maximum flow).
Each augmentation requires finding an augmenting path and updating residual capacities. A single search (DFS or BFS) over the graph and the capacity updates take O(E) time.
Multiplying the two bounds gives the overall runtime O(E * f).
Note: If you need a bound that depends only on graph size and not on capacities, use Edmonds–Karp (BFS-based implementation) which guarantees O(V * E^2) time; different algorithms give different trade-offs.
A video solution is available for this question — log in and enroll to watch it.