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 $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 duž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 $n$ minimizuje 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(V⁴)	Shimbel 1955
	O(V²EL)	Ford 1956
Bellman–Ford algoritam	O(VE)	Bellman 1958, Moore 1959
	O(V² log V)	Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dajkstrin algoritam sa listom	O(V²)	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 log_E/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 w_ij za svaku granu (i, j) u A, posmatrajmo program sa promenljivama x_ij

minimizuj

\sum _{ij\in A}w_{ij}x_{ij}

tako da je

x\geq 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}}

Vidi još уреди

IEEE_802.1aq
Stablo najkraćeg puta
Euklidov najkraći put
Pretraga u dva smera, algoritam koji pronalazi najkraći put između dva čvora u usmerenom grafu

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.