Največji pretok po omrežjuCEZAR, JURE (Avtor) Brodnik, Andrej (Mentor) omrežjezahtevnostnajvečji pretokalgoritemNamen dela je seznaniti bralca o algoritmih za iskanje največjega pretoka v omrežjih. Opisuje tri vrste algoritmov, njihovo delovanje in analizo. Prvi algoritem je Ford-Fulkersonov algoritem, ki je bil eden izmed prvih algoritmov za iskanje največjega pretoka. Drugi algoritem je zaporedni potisni in preimenuj, ki je eden izmed najhitrejših zaporednih algoritmov v današnjem času. Tretji algoritem je vzporedni potisni in preimenuj algoritem, ki je vzporedna pohitritev zaporednega potisni in preimenuj algoritma. Poleg algoritmov je v drugem poglavju opisana teorija omrežij, za lažje razumevanje delovanja algoritmov. V petem poglavju so zajeti vsi rezultati. Na začetku je časovna primerjava vseh treh algoritmov. V nadaljevanju se rezultati osredotočijo zgolj na vzporedni potisni in preimenuj algoritem, saj nas je zanimala pohitritev zaporednega potisni in preimenuj algoritma z vzporednim procesiranjem ter vplivom števila procesorjev na izvajanje vzporednega potisni in preimenuj algoritma. Pohitritev zaporednega algoritma se je kljub počasnejšemu delovanju na omrežjih z manj vozlišči izkazala za uspešno. Na omrežjih z velikim številom vozlišč smo zaporedni potisni in preimenuj algoritem pohitrili do 4-krat. Vzporedni potisni in preimenuj algoritem bi lahko še bolje optimizirali in s tem še dodatno pohitrili izvajanje, vendar to ni cilj te diplomske naloge.20202020-02-07 12:05:05Diplomsko delo/naloga113861VisID: 23323COBISS_ID: 1538527171sl