Problem najkraćeg puta

Из Википедије, слободне енциклопедије
(6, 4, 5, 1) i (6, 4, 3, 2, 1) su putevi između čvorova 6 i 1.

U teoriji grafova, problem nakraćeg puta je problem pronalaženja puta između dve tačke (ili čvora) u grafu tako da je zbir težina njegovih grana najmanji.

Ovo je analogno problemu nalaženja najkraćeg puta između dve raskrsnice na mapi puteva: čvorovi grafa odgovaraju raskrsnicama a grane ulicama, gde težine predstavljaju dužinu ulica.

Definicija[уреди]

Problem najkraćeg puta može biti definisan za bilo usmerene, neusmerene ili kombinovane grafove. Ovde je definisano za neusmerene grafove; za usmerene grafove definicija puta zahteva da uzastopni čvorovi budu povezani odgovarajućom usmerenom granom.

Dva čvora su susedna ako oba čvora povezuje jedna grana. Put u neusmerenom grafu je niz čvorova P = (v_1, v_2, \ldots, v_n ) \in V \times V \times \ldots \times V tako da v_i je susedno v_{i+1} za 1 \leq i < n. Takav put P je put duzžine n od v_1 do v_n. (v_i su promenljive; njihova oznaka ovde se odnosi na njihovu poziciju u nizu)

Neka e_{i, j} predstavlja granu koja povezuje čvorove v_i i v_j. Za težinsku funkciju f: E \rightarrow \mathbb{R}, i neusmereni graf G, najkraći put od v do v' je put P = (v_1, v_2, \ldots, v_n ) (gde v_1 = v i v_n = v') tako da za svako moguće nminimizuje sumu \sum_{i =1}^{n-1} f(e_{i, i+1}). Kada svaka grana u grafu ima težinu ili f: E \rightarrow \{1\}, to je ekvivalentno prolanaženju puta sa što manje grana.

Ovaj problem se takođe nekad naziva i problem najkraćeg puta jednog para, kako bismo ga razlikovali od sledećih varijacija:

  • problem najkraćeg puta sa jednim izvorom, gde se pronalazi najkraći put od izvornog čvora v do svih ostalih čvorova u grafu.
  • problem najkraćeg puta sa jednim odredištem, gde se pronalazi najkraći put od svih čvorova u usmerenom grafu do jednog odredišnog čvora v. Ovo može biti svedeno na problem najkraćeg puta sa jednim izvorom tako što se obrnu strelice u usmerenom grafu.
  • problem najkraćih puteva svih parova, gde se pronalazi najkraći put između svih parova čvorova v, v' u grafu.

Ove generalizacije imaju značajno efikasnije algoritme od korišćenja običnog algoritma za problem najkraćeg puta jednog para na svakom paru čvorova u grafu.

Algoritmi[уреди]

Najznačaniji algoritmi za rešavanje ovih problema su:

  • Dajkstrin algoritam rešava problem najkraćeg puta sa jednim izvorom.
  • Bellman–Ford algoritam rešava problem najkraćeg puta sa jednim izvorom ako težine grana mogu biti negativne.
  • Algoritam A* pretrage rešava problem najkraćeg puta jednog para using heuristics to try to speed up the search.
  • Flojd-Voršalov algoritam rešava problem najkraćeg puta svih parova.
  • Džonsonov algoritam rešava problem najkraćeg puta svih parova, i može biti brži od Flojd-Voršalovog algoritma na proređenim grafovima.

Mreža puteva[уреди]

Mreža puteva može da se posmatra kao graf sa pozitivnim težinama. Čvorovi predstavljaju raskrsnice a svaka grana grafa predstavlja ulicu između dve raskrsnice. Težina grane može da predstavlja dužinu ulice, vreme potrebno da se pređe ta ulica ili cena prelaska te ulice. Koristeći usmerene grafove možemo predstaviti i jednosmerne ulice. Ovakvi grafovi su posebni zato što su neke grane bitnije od drugih za dugačka putovanja (npr. autoputevi). Postoji veliki broj algoritama koji koriste ovo svojstvo i stoga su u mogućnosti da izračunaju najkraći put dosta brže nego što bi bilo moguće na opštim grafovima.

Svi ovi algoritmi rade u dve faze. U prvoj fazi, ovaj graf se pretprocesira bez znanja od izvornom ili odredišnom čvoru. Pva faza može potrajati nekoliko dana za realne podatke. Druga faza je faza upita. U ovoj fazi, izvorni i odredišni čvor su poznati. Trajanje druge faze je uglavnom manje od sekunde. Mreža puteva je statička, tako da se faza pretprocesiranja uradi jednom i može da se koristi za veliki broj upita na istoj mreži puteva.

Neki od poznatih algoritama za rešavanje problema najkraćeg puta[уреди]

Algoritam Vremenska složenost Autor
O(V4) Shimbel 1955
O(V2EL) Ford 1956
Bellman–Ford algoritam O(VE) Bellman 1958, Moore 1959
O(V2 log V) Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dajkstrin algoritam sa listom O(V2) Leyzorek et al. 1957, Dijkstra 1959
Dajkstrin algoritam sa modifikovanim binarnim hipom O((E + V) log V)
Dajkstrin algoritam sa Fibonačijevim hipom O(E + V log V) Fredman & Tarjan 1984, Fredman & Tarjan 1987
O(E log log L) Johnson 1982, Karlsson & Poblete 1983
Gabow algoritam O(E logE/V L) Gabow 1983b, Gabow 1985b
O(E + V√log L) Ahuja et al. 1990

Upotreba[уреди]

Algoritmi najkraćeg puta se koriste za automatsko pronalaženje puta između dve fizičke lokacije, kao što su uputstva pri vožnji na vebstranica kao što su Mapquest ili Google Maps. Za ovu svrhu koriste se specijalizovani brzi algoritmi.

Kod abstraktnih mašina, čiji čvorovi grafa predstavljaju stanja a grane opisuju moguće prelaze, algoritmi najkraćeg puta se koriste za pronalaženje optimalnog niza izbora kako bi se došlo do određenog stanja. Na primer, ako čvorovi predstavljaju stanja slagalice kao što je Rubikova Kocka i svaka usmerena grana odgovara jednom potezu, algoritmi najkraćeg puta se mogu koristiti da se pronađe rešenje sa najmanjim brojem poteza.

U mrežnom i telekomunikacionom domenu, ovaj problem najkraćeg puta se nekad naziva problemom puta sa najmanjim kašnjenjem i obično je povezan sa problemom najšireg puta.Na primer, algoritam može naći najkraći (sa najmanjim kašnjenjem) najširi put ili najširi (sa najmanjim kašnjenjem) najkraći put.

Zanimljiva upotreba ovih algoritama je igra "šest stepeni separacije" u kojoj se traži najkraći put u grafu kao što je pojavljivanje filmskih zvezda u istom filmu.

Takođe se koristi u robotici, transportaciji i VLSI dizajnu.

Slični problemi[уреди]

Za problem najkraćeg puta u kompjuterskoj geometriji, pogledaj Euklidov najkraći put.

Problem trgovačkog putnika je problem nalaženja najkraćeg puta koji prolazi kroz svaki čvor tačno jednom i vraća se u početak. Za razliku od problema najkraćeg puta, koji se može rešiti u polinomijalnom vremenu grafovima sa negativnim ciklusima, problem trgovačkog putnika je NP-kompleta i, kao takav, ne može se efikasno rešiti. Problem pronalaska najdužeg puta u grafu je takođe NP-kompletan problem.

Najkraći višestruki nepovezani put je reprezentacija primitivne mreže puteva u okviru Teorije termalnih pokreta makromolekula.

Problem ponovnog izračunavanja najkraćeg puta se pojavljuje ako dođe do određenih transformacija grafa (npr. smanjenje broja čvorova).

Problem najšireg puta traži put tako da je najmanja oznaka neke grane što veća.

Formulacija u linearanom programiranju[уреди]

Postoji formulacija problema najkraćeg puta u linearnom programiranju. Prilično je jednostavna u poređenju sa većinom ostalih algoritama u linearnom programiranju.

Za zadati usmereni graf (V, A) sa izvornim čvorom s, odredišnim čvorom t, i cenom wij za svaku granu (i, j) u A, posmatrajmo program sa promenljivama xij

minimizuj \sum_{ij \in A} w_{ij} x_{ij} tako da je x \ge 0 i za svako i, \sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1, &\text{ako }i=s;\\ -1, &\text{ako }i=t;\\ 0, &\text{ inače.}\end{cases}

Pogledajte još[уреди]