20.500.12556/RUL-168015 Problem najcenejšega pretoka na grafih Minimum-cost flow problem on graphs Reševanje problema najcenejšega pretoka igra ključno vlogo pri načrtovanju zasnove in arhitekture številnih sistemov v realnem svetu. Prav zaradi tega je potrebno, da imamo za reševanje problema hitre in učinkovite možnosti reševanja, ki nam zagotavljajo optimalno rešitev. V nalogi najprej opredelimo osnovne pojme in definicije, ki orišejo karakteristike problema. Nato podrobneje predstavimo metodo z odpravljanjem negativnih ciklov in metodo zaporednih najkrajših poti. Obe metodi, skupaj z metodo \textit{Simplex}, preizkusimo na naključno generiranih grafih in primerjamo rezultate. Na koncu metode poženemo še na podatkih cestnega omrežja Pirana in Ljubljane ter pokažemo njihovo učinkovitost še na primeru reševanja problemov iz realnega sveta. Solving the minimum cost flow problem plays a crucial role in the design and architecture of various real-world systems. Therefore, it is essential to have fast and efficient solution methods that guarantee an optimal result. In this work, we first define the fundamental concepts and definitions that outline the characteristics of the problem. We then present in detail the cycle-canceling method and the successive shortest path method. Both methods, along with the Simplex method, are tested on randomly generated graphs, and the results are compared. Finally, we apply the methods to road network data from Piran and Ljubljana to demonstrate their effectiveness in solving real-world problems. računalnik graf pretok omrežje algoritem zaporedne najkrajše poti odpravljanje ciklov computer graph costflow flow network algorithm successive shortest path cycle cancelling true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-03-25 11:00:02 2025-03-25 11:00:08 2025-04-15 11:48:12 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37461 232810499 Thuma_Vid_-_Problem_najcenejsega_pretoka_na_grafih.pdf Thuma_Vid_-_Problem_najcenejsega_pretoka_na_grafih.pdf 1 56B970246D3501BE87C70C0B8D99B561 99adf8dacb8f00b17777c0b2df7569b547d97c484612c961e0e789c36cea36b9 e8db7c0e-095e-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=200989 Fakulteta za računalništvo in informatiko 0 0 0