Џонсонов алгоритам

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Дзонсонов алгоритам је начин да се пронађу најкраћи путеви између свих парова чворова проређеног усмереног графа. Он омогућава да неке од тезина ивица буду негативне вредности, али не и циклуси негативне-тежине. Она ради користећи Белман-Фордов алгоритам за рачунање трансформације улазног графа која уклања све негативне тежине омогућавајући да се Дијкстра алгоритам користи на трансформисаном графу. Добио је назив по Доналду Б. Џонсону, који је први објавио ову технику 1977.

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

Опис алгоритма

Дзонсонов алгоритам се састоји из следећих корака:

Прво, нови чвор q се додаје графу, повезан ивицама тежине нула за сваки од чворова.
1. Друго, алгоритам се користи, почевши од новог чвора q, да нађе за сваки чвор в минималну тежину х(в) пута од q до в. Ако овај корак открије негативни циклус, алгоритам се прекида.
2. Следеће ивице оригиналног графа добијају нове тежине помоћу вредности израчунате од стране Белцман-Форд алгоритма: ивица од у до в, дужине w(у,в), дата је нова дужина w (у,в) + х (у) – х (в).
3. Коначно, q се уклања, а Дијкстра алгоритам се користи да пронађе најкраће путеве од сваког чвора с до сваког другог темена са новом вредности у графу.

Пример

Прве три фазе Дзонсон алгоритма су приказане на слици испод.

Граф на левој слици има две негативне ивице али нема негативних циклуса. У центру се приказују нова темена q, најкраћи пут стабла како је обрачунат по Белцман-Форд алгоритму са q као полазним теменом, а вредности х(в) израчунате на сваком другом чвору као дужина најкраћег пута од q до тог чвора. Имајте на уму да све ове вредности нису позитивне, јер q има нула дужину ивице од сваког чвора и најкраћи пут не може бити дужи од те ивице. Са десне стране је приказан граф нових вредности, формираних заменом тежине сваке ивице w(у,в)са w (у, в) + х (у) - х (в) . У овом графу са новим вредностима све тежине ивица су не-негативне, али најкраћи пут између било која два чвора користи исти низ ивица као најкраћи пут између два иста чвора у оригиналном графу. Алгоритам се завршава применом Дијкстра алгоритма за сваки од четири почетна чвора у графу нових вредности.

Исправност

У поновно измереном графу, сви путеви између пара с и т чворова имају исту количину х (с) - х (т) додату њима. Претходна изјава се мозе доказати на следећи начин: Нека је п с-т пут. Његова тежина W у поновно измереном графу је дата следећим изразом:

{\bigl (}w(s,p1)+h(s)-h(p1){\bigr )}+{\bigl (}w(p1,p2)+h(p1)-h(p2){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n})-h(t){\bigr )}.

Обратите пажњу да сваки $+h(p_{i})$ је отказан са $-h(p_{i})$ у претходном изразу угластим заградама, дакле, остаје нам следећи израз за W:

{\bigl (}w(s,p1)+w(p1,p2)+...+w(p_{n},t){\bigr )}+h(s)-h(t)

Обратите пажњу да у заградама израза је тежина п у оригиналној тежини.

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

Анализа

Временска слозеност овог алгоритма, користећи Фибоначијев хип у имплементацији Дијкстра алгоритма, је $О(V 2 лог V + ВЕ)$ : алгоритам користи $О(ВЕ)$ време у Белцман-Форд фази алгоритма, и $О(V лог V + Е)$ за сваки од $V$ инстанци Дијкстра алгоритма. Дакле, када је граф проређен, укупно време може да буде брже од Флојд-Варшаловог алгоритма, који решава исти проблем у времену $О(V 3)$ .

Референце

Блацк, Паул Е. (2004), „Јохнсон'с Алгоритхм”, Дицтионарy оф Алгоритхмс анд Дата Струцтурес, Натионал Институте оф Стандардс анд Тецхнологy .
Цормен, Тхомас Х.; Леисерсон, Цхарлес Е.; Ривест, Роналд L.; Стеин, Цлиффорд (2001). Интродуцтион то Алгоритхмс. МИТ Пресс анд МцГраw-Хилл. ИСБН 978-0-262-03293-3. . Сецтион 25.3, "Јохнсон'с алгоритхм фор спарсе грапхс". стр. 636–640.
Јохнсон, Доналд Б. (1977), „Еффициент алгоритхмс фор схортест патхс ин спарсе нетwоркс”, Јоурнал оф тхе АЦМ, 24 (1): 1—13, дои:10.1145/321992.321993 .
Суурбалле, Ј. W. (1974), „Дисјоинт патхс ин а нетwорк”, Нетwоркс, 14 (2): 125—145, дои:10.1002/нет.3230040204 .

Спољашње везе

Boost: All Pairs Shortest Paths