Problem najšireg puta

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 čvora u težinskom usmerenom grafu, povećavajući težinu minimalno-težinskih grana puta.

Na primer, ako graf predstavlja veze između rutera 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 Š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 problem minimax puta, koji traži put tako što minimizuje maksimalnu težinu svake grane. Primenjuje se tamo gde je uključeno planiranje transporta. Bilo koji problem najšireg puta može biti promenjen u algoritam problema minimax puta, ili obrnuto, tako što se preokrene smisao svih poređenja težina koja se dešavaju u algoritmu, ili ekvivalentno tako što se svaka grana zameni svojom negacijom.

Neusmereni grafovi

U neusmerenom grafu , najširi put može da se nađe kao put između dva čvora u maksimalnom razapinjućem stablu grafa, dok minimax put može da se nađe kao put između dva čvora u minimalnom razapinjućem stablu.

Za bilo koji graf, usmeren ili neusmeren, postoji jasan algoritam za traženje najšireg puta, čim je poznata težina ivice minimalne težine: jednostavno se obrišu sve manje grane i traži se bilo koji put između ostalih ivica koristeći obilazak stabla u širinu (BFS) ili obilazak stabla u dubinu (DFS). Na osnovu ovog testa, takođe postoji algoritam linearnog vremena za nalaženje najšireg s-t puta u neusmerenom grafu, koji ne koristi maksimalno razapinjuće stablo. Osnovna ideja algoritma je da se algoritam pretrage linearne vremenske složenosti primeni na grani srednje težine, i onda ili da se obrišu sve manje grane ili da se sve veće grane skupe u zavisnosti od toga da li put postoji ili ne postoji, i da se zatim rekurzivno smeste u manji rezultujući graf.

Fernandez, Garfinkel & Arbiol 1998 koriste usko grlo najkraćih puteva u cilju da sastave kompoziciju fotografija iz vazduha kombinovanjem više slika koje prikazuju preklapanje oblasti. U podproblemu gde se problem najšireg puta primenjuje, dve slike su već transformisane u običan koordinatni sistem; preostali zadatak je da se izabere šav, kriva koja prolazi kroz sve regije preklapanja i deli jednu sliku od druge. Pikseli na jednoj strani šava će biti kopirani sa jedne od slika, a pikseli na drugoj strani šava će biti kopirani sa druge slike; za razliku od ostalih metoda kompozicija koji seku piksele sa obe slike, ovaj metod proizvodi važeću fotografsku sliku svakog dela regije koji je uslikan. Oni mere težinu grana mrežastog grafa po numeričkoj proceni , koliko će šav kroz tu tačku da bude vidljiv; izbor najkraćeg puta kao šava, što je bolje nego konvencionalno traženje najkraćeg puta, primorava njihov sistem da nađe šav koga je teško razaznati, što je bolje nego dopustiti zamenu veće vidljivosti jednog dela slike za manju vidljivost bilo gde na slici.

Ako su težine svih grana neusmerenog grafa pozitivne, onda minimax udaljenost između parova tačaka (maksimalna težina ivica minimax puta) formira ultrametrički prostor (specijalna vrsta metričkog prostora); obrnuto svaki konačan ultrametrički prostor dolazi od minimax udaljenosti. Struktura podataka formirana od minimalnog razapinjućeg stabla dozvoljava da minimax udaljenost između bilo kog para čvorova bude izračunata za konstantno vreme u zavisnosti od udaljenosti, koristeći najmanjeg zajedničkog pretka u Dekartovom stablu (binarno stablo). Koren Dekartovog stabla predstavlja najtežu granu minimalnog razapinjućeg stabla, i deca korena su Dekartova stabla koja su rekurzivno formirana od podstabla minimalnog razapinjućeg stabla formiranog uklanjanjem najtežih grana. Listovi Dekartovog stabla predstavljaju čvorove ulaznog grafa, a minimax rastojanje između dva čvora je jednako težini čvora koji je najmanji zajednički predak Dekartovog stabla. Jednom kad je minimalno razapinjuće stablo sortirano, Dekartovo stablo se može konstruisati za linearno vreme.

Usmereni grafovi

U usmerenim grafovima, rešenje maksimalnog razapinjućeg stabla se ne može iskoristiti. Umesto toga, postoje nekoliko poznatih algoritama koji se mogu iskoristiti; koji algoritam izabrati zavisi od toga da li je početni ili odredišni čvor fiksiran, ili da li putevi više početnih ili odredišnih čvorova moraju istovremeno da se nađu.

Svi parovi

Problem najšireg puta svih parova ima primene u Šulcovoj metodi prilikom dobijanja pobednika u izborima gde glasači rangiraju kandidate prema prioritetu. Šulcova metoda formira kompletan usmeren graf u kome čvorovi predstavljaju kandidate i svaka dva čvora su povezana granom. Svaka grana je usmerena tako da izlazi iz čvora pobednika i ulazi u čvor gubitnika, pri čemu svaka grana predstavlja sopstveno malo takmičenje dva takmičara koji su povezani tom granom. Zatim, metoda računa najširi put između svih parova čvorova i pobednik je kandidat čiji čvor ima put do svakog protivnika koji je širi od puta koji protivnici imaju do njega. Rezultati izbora korišćenjem ove metode su dosledni Kondorsetovoj metodi (Condorcet method) kandidat koji je pobedio sva mala takmičenja je automatski pobedio na izboru – ali generalno dopušta da pobednik bude izabran, čak i u situacijama kada Kondorsetova metoda propadne. Šulcovu metodu su koristile različite organizacije, uključujući i Zadužbinu Vikimedije.

Da bi se izračunala najšira širina puta za sve parove čvorova u zbijenom usmerenom grafu, kao graf koji se javlja u primeni u glasanju, asimptotski najbrži mogući pristup ima vremensku složenost O(n^(3+ω)/2) gde je ω eksponent za brzo množenje matrica. Koristeći najbolje poznate algoritme za množenje matrica, vremenska složenost postaje O(n^2.688). Nasuprot tome, implementacija Šulcove metode koristi izmenjenu verziju jednostavnijeg Flojd-Varšalovog algoritma, i ima vremensku složenost O(n³). Za grafove koji su proređeni, bilo bi efikasnije da se više puta primeni algoritam najšireg puta sa pojedinačnim izvorom.

Jedan izvor

Ako su grane sortirane na osnovu svojih težina, onda izmenjena verzija Dijkstrinog algoritma može da računa uska grla između određenog početnog i svakog drugog čvora u grafu, za linearno vreme. Ključna ideja iza ubrzane konvencionalne verzije Dijkstrinog algoritma je da sekvenca rastojanja do svakog čvora, sa ciljem da se čvorovi uzimaju u obzir ovim algoritmom, je monotona podsekvenca svih sortiranih težinskih grana; stoga red sa prioritetom Dijkstrinog algoritma može biti zamenjen nizom brojeva od 1 do m (broj grana u grafu), gde član niza i sadrži čvorove čije rastojanje je težina grane na poziciji i u sortiranom redosledu. Ova metoda dozvoljava da se problem najšireg puta reši brzo koliko i sortiranje; na primer, ako je težina grane predstavljena kao ceo broj, onda bi se vreme koje je potrebno za sortiranje liste od m celih brojeva moglo primeniti na ovaj problem.

Jedan izvor i jedno odredište

Berman & Handler 1987 predlažu da bi servis vozila i vozila hitne pomoći trebalo da koriste minimax puteve kada se vraćaju u svoju bazu nakon poziva servisa. U ovoj primeni , vreme povratka nije toliko važno, za razliku od vremena reagovanja na mogući poziv servisa dok je vozilo servisa u povratku. Koristeći minimax putanju, gde je težina grane maksimalno vreme putovanja od jedne tačke grane do najudaljenijeg mogućeg poziva servisa, može se isplanirati ruta koja minimizuje maksimalno moguće vreme čekanja od trenutka kada servis primi poziv do trenutka kada vozilo servisa dođe na pozvano mesto. Ullah, Lee & Hassoun 2009 koriste maksimalne putanje kako bi napravili dominantnu lančanu reakciju u metaboličkim mrežama; u njihovom modelu, težina grane je slobodna energija metaboličke reakcije koja je predstavljena granom.

Još jedna primena najširih putanja se javlja u Ford-Fulkersonovom algoritmu za problem maksimalnog protoka. Više puta povećavajući protok duž maksimalnog kapaciteta puta u mreži protoka dovodi do male granice, O(m log U), brojeva povećanja koji su potrebni da bi se našao maksimalni protok; ovde, grane kapaciteta su podrazumevano celi brojevi, koji su u većini slučajeva U. Ipak, ova analiza nije pozdana za nalaženje puta koji ima maksimalni kapacitet; bilo koji put čiji kapacitet ima konstantan faktor maksimuma je dovoljan. Kombinujući ovu približnu ideju sa metodom povećanja najkraćeg puta Edmonds-Karpovog algoritma, dovodi do algoritma maksimalnog protoka koji je složenosti O(mn log U).

Moguće je vrlo efikasno naći putanje maksimalnog kapaciteta i minimax putanje sa pojedinačnim izvorom i pojedinačnim odredištem čak i u modelima računanja kod kojih ne smemo da vršimo bilo kakvu matematičku operaciju, možemo samo da upoređujemo grane ulaznog grafa. Algoritam sadrži set od S grana za koje se zna da predstavljaju usko grlo optimalnog puta; inicijalno, S je samo set svih m grana grafa. U svakoj iteraciji algoritma, S se deli na određene podsetove S₁, S₂, ... koje su približno istih veličina; broj podsetova u ovoj podeli nije slučajan, izabran je tako da se sve razdvojene tačke između podsetova mogu naći ponavljanjem srednjeg-traženja za vreme O(m). Algoritam zatim ponovo postavlja težinu svakoj grani grafa u zavisnosti od indeksa podseta kojoj grana pripada, i zatim se na tako izmenjenom grafu primeni izmenjeni Dijkstrin algoritam; i u zavisnosti od rezultata računanja, algoritam može za linearno vreme da odredi koji od podseta sadrži granu koja ima težinu uskog grla. Nakon toga se S zameni podsetom S_i, za koji se prethodno ustanovilo da sadrži granu uskog grla, i počinje sledeću iteraciju sa sada novim setom S. Broj podsetova na kojih se S može podeliti se eksponencijalno povećava svakim korakom, pa je broj iteracija proporcionalan logaritamskoj funkciji, O(log*n), dok je vremenska složenost ovog algoritma O(mlog*n).

Euklidov set tačaka

Varijanta problema minimax putanje se takođe uzela u obzir za set tačaka u Euklidovoj geometriji. Za razliku od neusmerenih grafova, ovaj problem može da se reši vrlo efikasno tako što se nađe Euklidovo minimalno razapinjajuće stablo. Ipak, postaje komplikovanije kada je put takav da ne minimizuje samo kratka rastojanja nego, među putanjama koje imaju ista kratka rastojanja, minimizuje ili približno minimizuje ukupnu dužinu puta. Približno rešenje se može dobiti korišćenjem tzv. geometrijskih izvijača.