An Approach to Efficient Network Flow Algorithm for Solving Maximum Flow Problem

Abstract

Network Flow Problems have always been among the best studied combinatorial optimization problems. These problems are central problems in operations research, computer science, and engineering and they arise in many real world applications. Flow networks are very useful to model real world problems like, current flowing through electrical networks, commodity flowing through pipes and so on. Maximum flow problem is the classical network flow problem. In this problem, the maximum flow which can be moved from the source to the sink is calculated without exceeding the maximum capacity. Once, the maximum flow problem is solved it can be used to solve other network flow problems also. Maximum flow problem is thoroughly studied in this thesis and the general algorithm is explained in detail to solve it. Then other network flow problems like, Minimam Cost Flow, Transshipment, Transportation, and Assignment problems are also briefly explained and shown that how they can be converted into maximum flow problem. The Ford-Fulkerson algorithm is the general algorithm which can solve all the network flow problems. The improvement of the Ford Fulkerson algorithm is Edmonds-Karp algorithm which uses BFS procedure instead of DFS to find an augmenting path. Next the modified Edmonds-Karp algorithm is designed to solve the maximum flow problem in efficient manner. One real world problem is taken, it is converted into network flow graph and the new algorithm is implemented to solve the problem. The same problem is solved using Edmonds-Karp algorithm also and both algorithms are compared in terms of different parameters. Finally, it is proved that the modified algorithm performs better in most cases and the new algorithm is implemented in C.