Problem najkraćeg puta

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.

(6, 4, 5, 1) i (6, 4, 3, 2, 1) su putevi između čvorova 6 i 1.

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 bilo za 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   tako da   je susedno   za  .

Takav put   je put dužine   od   do  .

(  su promenljive; njihova oznaka ovde se odnosi na njihovu poziciju u nizu)

Neka   predstavlja granu koja povezuje čvorove   i  .

Za težinsku funkciju  , i neusmereni graf  , najkraći put od   do   je put   (gde   i  ) tako da za svako moguće   minimizuje sumu   Kada svaka grana u grafu ima težinu ili  , 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:

  • 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.
  • 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   tako da je   i za svako i,  

Vidi jošУреди

ReferenceУреди

LiteraturaУреди

  • Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). „Fully dynamic output bounded single source shortest path problem”. Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms. Atlanta, GA. стр. 212—221. CiteSeerX 10.1.1.32.9856 . 
  • Dreyfus, S. E. (oktobar 1967). An Appraisal of Some Shortest Path Algorithms (PDF) (Извештај). Project Rand. United States Air Force. RM-5433-PR. Архивирано из оригинала (PDF) на датум 22. 02. 2017. Приступљено 25. 07. 2019.  DTIC AD-661265.