Gap Analysis of Ford-Fulkerson Algorithm and Edmonds-Karp Algorithm as Machine Learning Approach for Augmentation Path in the Maximum Flow Problem

Abstract

The maximum flow problem is popular with many researchers as it plays a significant role in many areas. This problem is about obtaining the maximum flow where there is one source and sink in the network flow. In solving maximum flow problems, many algorithms are applied such as the most used are the Ford-Fulkerson Algorithm and the Edmonds-Karp Algorithm. The goal of this study is to identify the gaps of these two algorithms and sufficiently provide an analysis and comparison of their time complexity, simplicity, and effectiveness to solve the augmentation path in the maximum flow problem. The Ford-Fulkerson and Edmonds-Karp algorithms performed well and sufficiently to solve the augmentation path in the maximum flow problem. However, both algorithms consist of different gaps like having slow time complexity and difficulty in implementation and execution.

 Keywords: Maximum Flow Problem, Augmentation Path, Ford Fulkerson Algorithm, Network Flow, Edmonds-Karp Algorithm

Received Date: July 14, 2021
Revised Date: August 18, 2021
Accepted Date: November 16, 2021