Implementacija in analiza algoritmov za problem maksimalnega pretoka v grafihPrimožič, Sašo (Avtor) Dobravec, Tomaž (Mentor) maksimalni pretokusmerjeni grafialgoritmianaliza učinkovitostikompleksnost algoritmovtestni primeriALGatorDIMACStopologija grafakapacitete povezavV 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.20252025-11-11 10:00:01Diplomsko delo/naloga175856VisID: 38318COBISS_ID: 259892739sl