Stručni rad

Guraj-Promijeni visinu algoritam za pronalaženje maksimalnog protoka mreže

Mario Zekić ; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet
Ivica Nakić ; Sveučilište u Zagrebu, Prirodoslovno matematički fakultet

Sažetak

Problem maksimalnog toka i njemu dualan problem, problem minimalnog reza, iznimno su korisni u modeliranju mnogih problema koji sadrže mreže, bilo cestovne, željezničke, računalne ili društvene. Obično modeliramo tok nekog materijala iz jednog dijela mreže u drugi, a tok mogu biti automobili, vlakovi, bitovi, preporuke i mnogi drugi predmeti i koncepti. Zanimljivo je da su se ova dva problema također pokazala korisnima u problemima modeliranja za koje nije očito da uključuju mreže ili protok materijala. Jedan takav primjer izložit ćemo u ovom članku.

U ovom članku izložit ćemo jedan od najefikasnijih poznatih algoritama za rješavanje problema maksimalnog toka, guraj-promijeni visinu algoritam za pronalaženje maksimalnog protoka mreže. Uz teorijsku pozadinu algoritma guraj-promijeni visinu, osvrnut ćemo se i na implementaciju tog algoritma u Javascriptu, kao i neke varijante algoritma koje nude određena poboljšanja.

Ključne riječi

optimizacija na grafovima; problem maksimalnog reza

Hrčak ID:

307610

URI

https://hrcak.srce.hr/307610

Datum izdavanja:

31.8.2023.

Posjeta: 444 *