Бржи алгоритам најкраћег пута
Бржи алгоритам најкраћег пута (БАНП) представља побољшање Беллман–Форд алгоритма који рачуна најкраће путеве са једним извором у усмереном тежинском графу. Алгоритам ради добро на насумичним проређеним графовима и посебно је погодан за графове који садрже гране са негативним тежинама. Алгоритам БАНП је објавио 1994. године Фандинг Дуан.
Алгоритам[уреди | уреди извор]
За задати усмерени тежински граф Г = (V, Е) и изворни чвор с, БАНП алгоритам проналази најкраћи пут од с до сваког чвора в у графу. Дужина најкраћег пута од с до в се чува у д(в) за сваки чвор в.
Основна идеја БАНП алгоритма иста је као и Беллман–Форд алгоритам по томе што сваки чвор се користи као кандидат да релаксира суседне чворове. Побољшање у односу на остале је у томе што уместо да покушава за све чворове слепо, БАНП одржава ред чворова кандидата и додаје чвор у ред само ако је тај чвор релаксиран. Овај процес се понавља док год нема више чворова који могу бити релаксирани.
Испод је псеудо-код овог алгоритма. Овде Q представља ред чворова кандидата, и w(у, в) је тежина гране (у, в).
procedure Shortest-Path-Faster-Algorithm(G, s) 1 for each vertex v ≠ s in V(G) 2 d(v) := ∞ 3 d(s) := 0 4 push s into Q 5 while Q is not empty 6 u := pop Q 7 for each edge (u, v) in E(G) 8 if d(u) + w(u, v) < d(v) then 9 d(v) := d(u) + w(u, v) 10 if v is not in Q then 11 push v into Q
Алгоритам се такође може применити на неусмерени граф тако што се замени свака неусмерена грана са две усмерене гране супротних смерова.
Просечни случај алгоритма[уреди | уреди извор]
За насумични граф, емпиријска просечна временска сложеност је О(|Е|).
Најгори случај алгоритма[уреди | уреди извор]
Претпоставимо да неко жели да пронађе најкраћи пут од чвора 1 до чвора н. Тада можемо додати грану (и, и + 1) са насумичном малом тежином за 1 ≤ и < н (тако да би најкраћи пут требао бити 1-2-...-н), и насумично додамо 4н других тешких грана. У овом случају, такозвани БАНП алгоритам ће бити врло спор.
Технике оптимизације[уреди | уреди извор]
Перформансе алгоритма су строго одређене редоследом којим чворови кандидати се користе да релаксирају остале чворове. У принципу, ако је Q ред са приоритетом, онда алгоритам заиста личи на Дијкстрин. Међутим, пошто се овде не користи ред са приоритетом, две технике се некад користе да унапреде квалитет реда, што унапређује и успешност просечног случаја (али не и успешност најгорег случаја). Обе технике преуређују редослед елемената у Q тако да су чворови ближи извору први процесуирани. Стога, када се имплементирају ове технике, Q више није ФИФО ред, већ нормална двострука листа.
Мале Ознаке Прво (МОП) техника. Псеудо-код:
procedure Small-Label-First(G, Q) if d(back(Q)) < d(front(Q)) then u := pop back of Q push u into front of Q
Велике Ознаке Задње (ВОЗ) техника. Псеудо-код:
procedure Large-Label-Last(G, Q) x := average of d(v) for all v in Q while d(front(Q)) > x u := pop front of Q push u to back of Q