Проблем најкраћег пута

(6, 4, 5, 1) и (6, 4, 3, 2, 1) су путеви између чворова 6 и 1.

У теорији графова, проблем накраћег пута је проблем проналажења пута између две тачке (или чвора) у графу тако да је збир тежина његових грана најмањи.

Ово је аналогно проблему налажења најкраћег пута између две раскрснице на мапи путева: чворови графа одговарају раскрсницама а гране улицама, где тежине представљају дужину улица.

Дефиниција

Проблем најкраћег пута може бити дефинисан било за усмерене, неусмерене или комбиноване графове.

Овде је дефинисано за неусмерене графове; за усмерене графове дефиниција пута захтева да узастопни чворови буду повезани одговарајућом усмереном граном.

Два чвора су суседна ако оба чвора повезује једна грана.

Пут у неусмереном графу је низ чворова $P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V$ тако да $v_{i}$ је суседно $v_{i+1}$ за $1\leq i<n$.

Такав пут $P$ је пут дужине $n$ од $v_{1}$ до $v_{n}$.

($v_{i}$ су променљиве; њихова ознака овде се односи на њихову позицију у низу)

Нека $e_{i,j}$ представља грану која повезује чворове $v_{i}$ и $v_{j}$.

За тежинску функцију $f:E\rightarrow \mathbb {R}$, и неусмерени граф $G$, најкраћи пут од $v$ до $v'$ је пут $P=(v_{1},v_{2},\ldots ,v_{n})$ (где $v_{1}=v$ и $v_{n}=v'$) тако да за свако могуће $n$ минимизује суму $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ Када свака грана у графу има тежину или $f:E\rightarrow \{1\}$, то је еквивалентно проланажењу пута са што мање грана.

Овај проблем се такође некад назива и проблем најкраћег пута једног пара, како бисмо га разликовали од следећих варијација:

• проблем најкраћег пута са једним извором, где се проналази најкраћи пут од изворног чвора в до свих осталих чворова у графу.

• проблем најкраћег пута са једним одредиштем, где се проналази најкраћи пут од свих чворова у усмереном графу до једног одредишног чвора в. Ово може бити сведено на проблем најкраћег пута са једним извором тако што се обрну стрелице у усмереном графу.

• проблем најкраћих путева свих парова, где се проналази најкраћи пут између свих парова чворова в, в' у графу.

Ове генерализације имају значајно ефикасније алгоритме од коришћења обичног алгоритма за проблем најкраћег пута једног пара на сваком пару чворова у графу.

Алгоритми

Најзначанији алгоритми за решавање ових проблема су:

• Дајкстрин алгоритам решава проблем најкраћег пута са једним извором.

• Беллман–Форд алгоритам решава проблем најкраћег пута са једним извором ако тежине грана могу бити негативне.

• Алгоритам А* претраге решава проблем најкраћег пута једног пара усинг хеуристицс то трy то спеед уп тхе сеарцх.

• Флојд-Воршалов алгоритам решава проблем најкраћег пута свих парова.

• Џонсонов алгоритам решава проблем најкраћег пута свих парова, и може бити бржи од Флојд-Воршаловог алгоритма на проређеним графовима.

Мрежа путева

Мрежа путева може да се посматра као граф са позитивним тежинама. Чворови представљају раскрснице а свака грана графа представља улицу између две раскрснице. Тежина гране може да представља дужину улице, време потребно да се пређе та улица или цена преласка те улице. Користећи усмерене графове можемо представити и једносмерне улице. Овакви графови су посебни зато што су неке гране битније од других за дугачка путовања (нпр. аутопутеви). Постоји велики број алгоритама који користе ово својство и стога су у могућности да израчунају најкраћи пут доста брже него што би било могуће на општим графовима.

Сви ови алгоритми раде у две фазе. У првој фази, овај граф се претпроцесира без знања од изворном или одредишном чвору. Пва фаза може потрајати неколико дана за реалне податке. Друга фаза је фаза упита. У овој фази, изворни и одредишни чвор су познати. Трајање друге фазе је углавном мање од секунде. Мрежа путева је статичка, тако да се фаза претпроцесирања уради једном и може да се користи за велики број упита на истој мрежи путева.

Неки од познатих алгоритама за решавање проблема најкраћег пута

Алгоритам	Временска сложеност	Аутор
	О(V4)	Схимбел 1955
	О(V2ЕЛ)	Форд 1956
Беллман–Форд алгоритам	О(ВЕ)	Беллман 1958, Мооре 1959
	О(V2 лог V)	Дантзиг 1958, Дантзиг 1960, Минтy (цф. Поллацк & Wиебенсон 1960), Wхитинг & Хиллиер 1960
Дајкстрин алгоритам са листом	О(V2)	Леyзорек ет ал. 1957, Дијкстра 1959
Дајкстрин алгоритам са модификованим бинарним хипом	О((Е + V) лог V)
Дајкстрин алгоритам са Фибоначијевим хипом	О(Е + V лог V)	Фредман & Тарјан 1984, Фредман & Тарјан 1987
	О(Е лог лог L)	Јохнсон 1982, Карлссон & Поблете 1983
Габоw алгоритам	О(Е логЕ/V L)	Габоw 1983б, Габоw 1985б
	О(Е + V√лог L)	Ахуја ет ал. 1990

Употреба

Алгоритми најкраћег пута се користе за аутоматско проналажење пута између две физичке локације, као што су упутства при вожњи на вебстраница као што су Мапqуест или Гоогле Мапс. За ову сврху користе се специјализовани брзи алгоритми.

Код абстрактних машина, чији чворови графа представљају стања а гране описују могуће прелазе, алгоритми најкраћег пута се користе за проналажење оптималног низа избора како би се дошло до одређеног стања. На пример, ако чворови представљају стања слагалице као што је Рубикова Коцка и свака усмерена грана одговара једном потезу, алгоритми најкраћег пута се могу користити да се пронађе решење са најмањим бројем потеза.

У мрежном и телекомуникационом домену, овај проблем најкраћег пута се некад назива проблемом пута са најмањим кашњењем и обично је повезан са проблемом најширег пута.На пример, алгоритам може наћи најкраћи (са најмањим кашњењем) најшири пут или најшири (са најмањим кашњењем) најкраћи пут.

Занимљива употреба ових алгоритама је игра "шест степени сепарације" у којој се тражи најкраћи пут у графу као што је појављивање филмских звезда у истом филму.

Такође се користи у роботици, транспортацији и ВЛСИ дизајну.

Слични проблеми

За проблем најкраћег пута у компјутерској геометрији, погледај Еуклидов најкраћи пут.

Проблем трговачког путника је проблем налажења најкраћег пута који пролази кроз сваки чвор тачно једном и враћа се у почетак.

За разлику од проблема најкраћег пута, који се може решити у полиномијалном времену графовима са негативним циклусима, проблем трговачког путника је НП-комплета и, као такав, не може се ефикасно решити. Проблем проналаска најдужег пута у графу је такође НП-комплетан проблем.

Најкраћи вишеструки неповезани пут је репрезентација примитивне мреже путева у оквиру Теорије термалних покрета макромолекула.

Проблем поновног израчунавања најкраћег пута се појављује ако дође до одређених трансформација графа (нпр. смањење броја чворова).

Проблем најширег пута тражи пут тако да је најмања ознака неке гране што већа.

Формулација у линеараном програмирању

Постоји формулација проблема најкраћег пута у линеарном програмирању. Прилично је једноставна у поређењу са већином осталих алгоритама у линеарном програмирању.

За задати усмерени граф (V, А) са изворним чвором с, одредишним чвором т, и ценом w_иј за сваку грану (и, ј) у А, посматрајмо програм са променљивама x_иј

минимизуј $\sum _{ij\in A}w_{ij}x_{ij}$ тако да је $x\geq 0$ и за свако и, $\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}}$

Види још

• ИЕЕЕ_802.1аq
• Стабло најкраћег пута
• Еуклидов најкраћи пут
• Претрага у два смера, алгоритам који проналази најкраћи пут између два чвора у усмереном графу

Литература

• Фригиони, D.; Марцхетти-Спаццамела, А.; Нанни, У. (1998). „Фуллy дyнамиц оутпут боундед сингле соурце схортест патх проблем”. Проц. 7тх Анну. АЦМ-СИАМ Сyмп. Дисцрете Алгоритхмс. Атланта, ГА. стр. 212—221. ЦитеСеерX 10.1.1.32.9856 . 
• Дреyфус, С. Е. (октобар 1967). Ан Аппраисал оф Соме Схортест Патх Алгоритхмс (ПДФ) (Извештај). Пројецт Ранд. Унитед Статес Аир Форце. РМ-5433-ПР. Архивирано из оригинала (ПДФ) 22. 02. 2017. г. Приступљено 25. 07. 2019.  ДТИЦ АД-661265.