20.500.12556/RUL-175856 Implementacija in analiza algoritmov za problem maksimalnega pretoka v grafih Analysis and implementation of algorithms for the maximum flow problem in graphs V diplomski nalogi obravnavamo problem maksimalnega pretoka v grafih, ki ima pomembno vlogo pri reševanju številnih optimizacijskih nalog. Predstavljena je rešitev, ki vključuje implementacijo in analizo učinkovitosti znanih algoritmov za iskanje maksimalnega pretoka: Ford-Fulkersonov algoritem, Edmonds-Karpov algoritem, Dinitzov algoritem in različice algoritma tipa potisni–povišaj. Za potrebe testiranja smo ustvarili različne vhodne primere, ki vključujejo naključne grafe, redke in goste grafe, grafe z različno porazdeljenimi kapacitetami povezav ter različne topologije. Dodatno smo uporabili tudi realne probleme iz nabora DIMACS, kot so primeri s področja superločljivosti in dekonvolucije tekstur. Testiranje in primerjavo algoritmov smo izvedli s pomočjo sistema ALGator, ki omogoča učinkovito in ponovljivo izvajanje eksperimentov. Rezultati s pomočjo tabel in grafov prikazujejo časovno zahtevnost, število posameznih operacij, stabilnost in splošno učinkovitost posameznih algoritmov. Ugotovili smo, da na učinkovitost algoritmov bistveno vplivajo značilnosti vhodnih podatkov. Pri kompleksnejših problemih se starejši algoritmi, kot sta Ford-Fulkersonov algoritem in Edmonds-Karpov algoritem, izkažejo kot neučinkoviti. Naprednejši algoritmi, kot so Dinitzov algoritem in algoritmi družine potisni–povišaj, dosegajo bistveno boljše rezultate. 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. maksimalni pretok usmerjeni grafi algoritmi analiza učinkovitosti kompleksnost algoritmov testni primeri ALGator DIMACS topologija grafa kapacitete povezav maximum flow directed graphs algorithms efficiency analysis algorithm complexity test cases ALGator DIMACS graph topology edge capacities true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-11-11 10:00:01 2025-11-11 10:00:10 2025-12-15 04:08:11 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38318 259892739 Primozic_Saso_-_Implementacija_in_analiza_algoritmov_za_problem_maksimalnega_pretoka_v_grafih.pdf Primozic_Saso_-_Implementacija_in_analiza_algoritmov_za_problem_maksimalnega_pretoka_v_grafih.pdf 1 3321047A00C931155AC6BE24ECF6FCA7 4c0358165b0f5d5e0fa5d7ac52df45968c827cd7de0a7e1cd155f09efa278f17 7f443a4f-bedc-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=221764 Fakulteta za računalništvo in informatiko 0 0 0