Problem najšireg puta — разлика између измена
Садржај обрисан Садржај додат
м Робот: додато {{subst:User:Autobot/sandbox2}} |
Поправљене везе: čvor → Čvor (informatika) користећи Dab solver |
||
Ред 2:
[[Датотека:TezinskiGraf.jpg|мини|U ovom grafu, najširi put od cvora D do cvora F je opsega 29, i prolazi kroz čvorove C, E, B i G]]
U [[algoritmima za rad sa grafovima]] , '''problem najšireg puta''', takođe poznat kao '''problem usko grlo najkraćeg puta''' ili '''problem maksimalnog kapaciteta puta''', je problem nalaženja puta između dva određena [[Čvor (informatika)|čvor]]a u težinskom usmerenom grafu, povećavajući težinu minimalno-težinskih grana puta.
Na primer, ako graf predstavlja veze između [[ruter]]a na [[Интернет|Internetu]], i težina grane predstavlja protok konekcije između dva rutera, problem najšireg puta je problem nalaženja puta između dva Internet čvora koja imaju maksimalni mogući protok. Težina grane minimalne težine je poznata kao kapacitet protoka puta. Pored primene u mreži rutera, problem najšireg puta je vrlo važna komponenta [[Šulcova metoda|Šulcove metode]] (sistem za glasanje), prilikom odlučivanja pobednika izbora. Takođe problem se primenjuje u tzv. digitalnom sastavljanju (proces digitalne montaže više slika u jednu završnu sliku) , u metaboličkoj analizi, i u računanju maksimalnog toka. Moguće je prilagoditi algoritme najkraćeg puta kako bi se izračunao najširi put, menjajući ih tako da koriste udaljenost uskog grla umesto dužine puta. Dobro je znati da, u mnogim slučajevima čak i brži algoritmi su mogući.
Usko povezan problem sa ovim problemom je
== Neusmereni grafovi ==
Ред 85:
== Reference ==
{{reflist
{{DEFAULTSORT:Проблем најширег пута}}
| |||