Abstract:
Graph is an effective data structure to solve the complex problems in Computer
Sciences. Maximum Flow Problem is one of those problems, which are based on
Graph data structure. The basic problem of finding a maximal flow in a network
occurs not only in transportation and communication networks but also in
currency arbitrage, image enhancement, machine scheduling and many other
applications.
There are many algorithms designed to solve the maximum flow problems. The
Edmond Karp algorithm is also included in the list of those algorithms, which
provides the efficient and optimal solution for the maximum problems. It is
upgraded version of Ford Fulkerson Method. The performance of the Edmond
Karp algorithm is better than the Ford Fulkerson Method regarding to searching
of paths in network graph. Edmond Karp algorithm uses the Breadth-first search
(BFS) algorithm to find the augmenting paths in the network graph [6].
In this research, the performance of the Edmond Karp algorithm is analysed and
evaluated through a given conditions in the form of input data. For this purpose,
simulation is designed to monitors the efficiency of the algorithm in respect of
different output parameters, like running time, number of paths and maximum
flow.
The concept of the busy node is also elaborated in this research work. Busy node
is the particular node in the network graph, which is existed in maximum number
of augmenting paths. Normally it contains maximum share of the flow in the
graph. The idea of the busy node can be utilized for optimal solutions of image
processing and network related problems.
The simulation uses datasets for the experimental evaluation of the Edmond Karp
algorithm. These datasets are collected through different methods: first one
includes “Auto Generated Random Graphs” and other is “User Defined Graphs”.
The simulation is also stored the experiment results to observe the behaviour of
the algorithm. At the end of this report, cumulative average time is calculated
from the experiment results. These cumulative average times indicate the best as
well as worst case scenarios of the algorithm. In best case, it produces 2.851ms
and in worst case 19.7143ms.
