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 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 ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V}$ tako da ${\displaystyle v_{i}}$ je susedno ${\displaystyle v_{i+1}}$ za ${\displaystyle 1\leq i<n}$.

Takav put ${\displaystyle P}$ je put dužine ${\displaystyle n}$ od ${\displaystyle v_{1}}$ do ${\displaystyle v_{n}}$.

(${\displaystyle v_{i}}$ su promenljive; njihova oznaka ovde se odnosi na njihovu poziciju u nizu)

Neka ${\displaystyle e_{i,j}}$ predstavlja granu koja povezuje čvorove ${\displaystyle v_{i}}$ i ${\displaystyle v_{j}}$.

Za težinsku funkciju ${\displaystyle f:E\rightarrow \mathbb {R} }$, i neusmereni graf ${\displaystyle G}$, najkraći put od ${\displaystyle v}$ do ${\displaystyle v'}$ je put ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ (gde ${\displaystyle v_{1}=v}$ i ${\displaystyle v_{n}=v'}$) tako da za svako moguće ${\displaystyle n}$ minimizuje sumu ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ Kada svaka grana u grafu ima težinu ili ${\displaystyle 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^4)	Shimbel 1955 harvnb грешка: no target: CITEREFShimbel1955 (help)
	O(V^2EL)	Ford 1956 harvnb грешка: no target: CITEREFFord1956 (help)
Bellman–Ford algoritam	O(VE)	Bellman 1958 harvnb грешка: no target: CITEREFBellman1958 (help), Moore 1959 harvnb грешка: no target: CITEREFMoore1959 (help)
	O(V^2 log V)	Dantzig 1958 harvnb грешка: no target: CITEREFDantzig1958 (help), Dantzig 1960 harvnb грешка: no target: CITEREFDantzig1960 (help), Minty (cf. Pollack & Wiebenson 1960 harvnb грешка: no target: CITEREFPollackWiebenson1960 (help)), Whiting & Hillier 1960 harvnb грешка: no target: CITEREFWhitingHillier1960 (help)
Dajkstrin algoritam sa listom	O(V^2)	Leyzorek et al. 1957 harvnb грешка: no target: CITEREFLeyzorekGrayJohnsonLadew1957 (help), Dijkstra 1959 harvnb грешка: no target: CITEREFDijkstra1959 (help)
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 harvnb грешка: no target: CITEREFFredmanTarjan1984 (help), Fredman & Tarjan 1987 harvnb грешка: no target: CITEREFFredmanTarjan1987 (help)
	O(E log log L)	Johnson 1982 harvnb грешка: no target: CITEREFJohnson1982 (help), Karlsson & Poblete 1983 harvnb грешка: no target: CITEREFKarlssonPoblete1983 (help)
Gabow algoritam	O(E logE/V L)	Gabow 1983b harvnb грешка: no target: CITEREFGabow1983b (help), Gabow 1985b harvnb грешка: no target: CITEREFGabow1985b (help)
	O(E + V√log L)	Ahuja et al. 1990 harvnb грешка: no target: CITEREFAhujaMehlhornOrlinTarjan1990 (help)

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 ${\displaystyle \sum _{ij\in A}w_{ij}x_{ij}}$ tako da je ${\displaystyle x\geq 0}$ i za svako i, ${\displaystyle \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.