Бржи алгоритам најкраћег пута

Бржи алгоритам најкраћег пута (БАНП) представља побољшање Беллман–Форд алгоритма који рачуна најкраће путеве са једним извором у усмереном тежинском графу. Алгоритам ради добро на насумичним проређеним графовима и посебно је погодан за графове који садрже гране са негативним тежинама. Алгоритам БАНП је објавио 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