Problem maksimalnog protoka
| Autor: | Piplica, Jelena |
|---|---|
| Přispěvatelé: | Perić, Jurica, Klaričić Bakula, Milica, Laštre, Ana |
| Jazyk: | chorvatština |
| Rok vydání: | 2023 |
| Předmět: |
put
arc Ford-Fulkerson algorithm digraph Dijkstra algoritam augmenting path rezidualni kapacitet PRIRODNE ZNANOSTI. Matematika Ford-Fulkerson algoritam težinska funkcija minimalni rez Dijkstra’s algorithm graf rezidualni graf Bellman-Ford algoritam residual capacity weight function Bellman-Ford algorithm path digraf stablo graph tree minimum cut uvećavajući put network mreža residual graph NATURAL SCIENCES. Mathematics luk |
| Popis: | Dijkstra algoritam i Bellman-Ford algoritam su algoritmi koji se koriste za pronalaženje najkraćeg puta u težinskom grafu. Dijkstra algoritam djeluje na pozitivnim težinama bridova i koristi se za pronalaženje najkraćeg puta od jednog početnog vrha do svih ostalih vrhova u grafu. Bellman-Ford algoritam, s druge strane, može se koristiti čak i kada postoje negativne težine bridova, ali ima složenost vremena veću od Dijkstra algoritma. Ford-Fulkerson algoritam koristi se za pronalaženje maksimalnog mrežnog protoka, a temelji se na uvećavajućim putevima. Ovaj algoritam iterativno pronalazi uvećavajuće puteve i uvećava protok dok ne postigne maksimalni protok. Ovi algoritmi su važan alat za rješavanje različitih problema u području grafova i optimizacije. Dijkstra’s algorithm and Bellman-Ford algorithm are algorithms used to find the shortest path in a weighted graph. Dijkstra’s algorithm works with positive edge weights and is used to find the shortest path from a single source node to all other nodes in the graph. On the other hand, the Bellman-Ford algorithm can handle graphs with negative edge weights but has a higher time complexity compared to Dijkstra’s algorithm. The Ford-Fulkerson algorithm is used to find the maximum flow in a network and is based on augmenting paths. This algorithm iteratively finds augmenting paths and increases the flow until it reaches the maximum flow. All algorithms are important tools for solving various graph and optimization problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|