In this thesis, we address the maximum flow problem in graphs, which plays
an important role in solving numerous optimization tasks. We present a
solution that includes the implementation and performance analysis of well known
algorithms for finding the maximum flow: the Ford–Fulkerson algorithm,
the Edmonds–Karp algorithm, Dinic’s (Dinitz’s) algorithm, and
variants of the push–relabel algorithm.
For testing purposes, we created various input instances, including random
graphs, sparse and dense graphs, graphs with differently distributed
edge capacities, and different topologies. Additionally, we used real problems
from the DIMACS benchmark set, such as cases from the domains of
super-resolution and texture deconvolution. The testing and comparison of
the algorithms were carried out using the ALGator system, which enables
efficient and reproducible execution of experiments.
The results, presented with tables and charts, show the time complexity,
the number of individual operations, stability, and the overall efficiency of
the individual algorithms. We found that the characteristics of the input
data significantly affect algorithm performance. For more complex problems,
older algorithms such as Ford–Fulkerson and Edmonds–Karp prove
inefficient, while more advanced algorithms, such as Dinitz’s algorithm and
the push–relabel family, achieve significantly better results.
|
