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.

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:
 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

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š 
 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 
 
  DTIC AD-661265.

Grafovski algoritmi
Рачунарски проблеми у теорији графова
Едсгер Дајкстра
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 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 : 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 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š 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 DTIC AD-661265 . Grafovski algoritmi Рачунарски проблеми у теорији графова Едсгер Дајкстра