Why is Edmond Karps faster than Ford-Fulkerson?

Question

Why choosing the shortest augmentation path everytime instead of an arbitrary augmentation path makes the Edmond Karps algorithm faster than Ford-Fulkerson

Answer 1

Ford-fulkerson algorithms uses DFS or a random order to traverse through the network which indicates that it can select any augmenting path, which may not be necessarily be the shortest. In this case, arbitrary paths can lead to more frequent revisits and potential cycles, leading to inefficiencies. Ford-Fulkerson’s arbitrary paths can result in a significantly larger number of augmentations due to potential cycles and redundant paths.

As a result the, time complexity of ford-fulkerson algorihtms would be O(E.F), where E is the number of edges and F is the maximum flow. This is not efficient because it is dependent upon the value of capacities or we can say the input by the user.

Whereas, Edmonds-Karp uses BFS which ensures that shortest augmenting path is taken every time. Each augmentation increases the shortest path length monotonically. This minimizes the chance of revisiting paths and optimizes the flow increments. the shortest path approach ensures a bounded number of augmentations. The maximum number of augmenting paths can be directly related to the number of vertices |V|, making it predictable and manageable.

As a result, the time complexity of edmonds-karp would be O(V.E^2), which reduces its dependency on the input. Although, it does have a polynomial time complexity but still it is better than ford-fulkerson algorithm.

The following image displays the scenario in which edmonds-karp outperform ford-fulkerson: