Најкраћи путеви у графу¶

Најкраћи путеви из једног чвора - Дајкстрин алгоритам¶

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

Алгоритам ради индуктивно, тако што се претпоставља да се након \(k\) корака извршавања алгоритма познају \(k\) чворова који су најближи почетном чвору (укључујући и њега), као и најкраћа растојања од почетног чвора до њих. Нека они чине скуп чворова \(V_k = \{v_0, \ldots, v_{k-1}\}\). Почетни чвор је сигурно најближи сам себи и растојање до њега је једнако нули, па је база индукције скуп \(V_1 = \{v_0\}\) који садржи само почетни чвор. Поставља се питање како извршити идуктивни корак тј. како да се одреди наредни најближи чвор \(v_{k}\). Најкраћи пут од почетног чвора \(v_0\) до чвора \(v_k\) може да садржи само чворове из \(V_k\) (на том путу не може постојати неки чвор ван \(V_k\), јер би тај чвор био ближи почетном чвору од чвора \(v_k\)). Према томе, да бисмо пронашли чвор \(v_k\), треба проверити све гране које спајају чворове из \(V_k\) са чворовима који нису у \(V_k\) (остале гране се могу ингорисати). У сваком кораку се скуп \(V_k\) проширује чвором \(v_k \notin V_k\) за који је најмања вредност \(\min\{r(v_0, v_i) + d(v_i, v_k)\ |\ v_i \in V_k\}\), где је \(r(v_0, v_i)\) дужина најкраћег пута од почетног чвора \(v_0\) до \(v_i\) (који је познат на основу индуктивне хипотезе), а \(d(v_i, v_k)\) дужина гране од чвора \(v_i\) до \(v_k\).

Овим је алгоритам у потпуности прецизиран и могуће је дати опис алгоритма у пседукоду. Вредности \(r(v_0, v_i)\) најкраћих растојања за чворове \(v_i\) скупа \(V_k\) које су већ одређене се памте у низу r и обележавамо их са r[vi].

postavi Vk={v0}
postavi najkrace rastojanje r[v0] = 0
dok skup Vk ne sadrzi sve cvorove grafa:
    odaberi par corova vi ∈ Vk i vk ∉ Vk za koji se postiže
       najmanja vrednost r[vi] + d(vi, vk)
    ubaci cvor vk u Vk
    postavi najkrace rastojanje r[vk] = r[vi] + d(vi, vk)
za svaki cvor vi najkrace rastojanje je r[vi]

Значајна неефикасност претходног алгоритма настаје због анализе свих парова чворова \((v_i, v_k)\) у сваком кораку. Ефикаснија имплементација се може добити ако се за сваки чвор \(v\) ван \(V_k\) у једном низу памти вредност

која процењује најкраће растојање од чвора \(v_0\) до чвора \(v\) (али само преко чворова из \(V_k\)). За чворове који нису достижни на овај начин, у низу се памти вредност \(r_v = +\infty\), док за чворове \(v_i \in V_k\) важи да је \(r_{v_i} = r(v_0, v_i)\) тј. у низу се памте стварне вредности најкраћих растојања од \(v_0\).

Вредност \(r_v\) се може израчунавати инкрементално. Када се нови чвор дода у \(V_k\) потребно је ажурирати само вредности \(r_v\) њему суседних чворова. Претпоставимо да се у скуп \(V_k\) додаје чвор \(v_k\) и тако добија \(V_{k+1}\). За сваки чвор \(v\) суседан чвору \(v_k\) нова вредност \(r'_v\) једнака је

Заиста, пошто је \(V_{k+1} = V_k \cup \{v_k\}\) важи да је

Ова модификација се описује следећим псеудокодом (у претходном алгоритму низ \(r\) је садржао само најкраћа растојања до чворова у \(V_k\), а у овом поред тога садржи и процене најкраћих растојања до чворова ван \(V_k\) које пролазе само преко чворова из \(V_k\)).

postavi r[v0]=0 i r[vi]=∞ za ostale cvorove vi
postavi Vk={v0}
dok skup Vk ne sadrzi sve cvorove grafa:
    odaberi k takvo da vk nije u Vk, za koje se postiže najmanja vrednost r[k]
    ubaci cvor vk u Vk
    za sve susede vj cvora vk:
       postavi r[vj] na min(r[vj], r[vk] + d(vk, vj))
za svaki cvor vi najkrace rastojanje je r[vi]

У наредној анимацији је приказан рад овог алгоритма на једном примеру. Свака врста табеле са десне стране садржи тренутну процену растојања сваког чвора од почетног (почетни је чвор 0) и те процене се мало по мало приближавају стварним вредностима најкраћих растојања од почетног чвора. Чворови скупа \(V_k\) су обојени зеленом бојом.

Ова анимација је креирана коришћењем веб-апликације доступне на сајту Математичког факултета у Београду (http://www.matf.bg.ac.rs/~filip/algoritmi/dajkstra.html). Покушај да коришћењем ове апликације тестираш своје досадашње разумевање алгоритма (за граф који ти буде приказан попуни таблицу, па провери да ли си је добро попунио/попунила)

У наставку дајемо опис алгоритма у оригиналном облику (онако како га је описао Дајкстра). У сваком кораку алгоритма скуп чворова је подељен на:

• скуп \(A\) који садржи чворове до којих је познато најкраће растојање (то је скуп \(V_k\) из претходног описа) и

• скуп \(B\) који садржи чворове до којих још није познато најкраће растојање.

Скуп \(B\) се може поделити на скуп \(B_1\) који садржи чворове који су помоћу једне гране повезани са чворовима из скупа \(A\) и скуп \(B_2\) који садржи остале чворове скупа \(B\).

Скуп грана се у сваком кораку алгоритма може разложити на:

• скуп \(I\) који садржи гране на најкраћим путевима од почетног чвора до чворова из скупа \(A\) (те гране су у претходној анимацији обојене зелено)

• скуп \(II\) који повезује чворове из скупа \(A\) са чворовима из скупа \(B_1\) – за сваки чвор из \(B_1\) овај скуп садржи тачно једну грану и то ону која даје најкраћи пут до тог чвора узевши у обзир све чворове из \(A\) (те гране су у претходној анимацији обојене наранџасто).

• скуп \(III\) који садржи остале гране. То су гране које су или избачене из разматрања јер је закључено да нису део најкраћих путева (оне су у претходној анимацији обојене црвено) или још нису размотрене (оне су у претходној анимацији нацртане танко, црном бојом)

У старту су сви чворови у скупу \(B_2\) а све гране у скупу \(III\). Најближи чвор почетном је сам почетни чвор (до њега је растојање 0). Зато се почетни чвор пребацује у скуп \(A\) и понављају се следећа два корака:

• корак 1: разматрају се све гране \(e\) које повезују чвор \(u\) који је управо убачен у \(A\) са чворовима \(v\) из скупа \(B\). Ако чвор \(v\) припада скупу \(B_1\) проверава се да ли је пут од почетног чвора до чвора \(v\) краћи ако се иде преко чвора \(u\) и преко гране \(e\), него ако се иде преко чвора \(u\) и преко гране \(e'\) из скупа \(II\) која је повезивала \(v\) са чворовима из \(A\) (пре додавања чвора \(u\) у скуп \(A\)). Ако је нови пут краћи грана \(e\) мења грану \(e'\) у скупу \(II\), а у супротном грана \(e\) се одбацује. Ако чвор \(v\) припада скупу \(B_2\), тада он раније није био повезан са чворовима из \(A\) и грана \(e\) се додаје у скуп \(II\).

• корак 2: Сваки чвор у скупу \(B_1\) се може повезати са почетним чвором на јединствен начин ако се разматрају само гране из скупова \(I\) и \(II\). На тај начин је одређено јединствено растојање од почетног чвора до сваког чвора у скупу \(B_1\) (растојање до чворова из \(B_2\) се може сматрати \(+\infty\)). Чвор из скупа \(B_1\) са најкраћим растојањем од почетног чвора се пребацује у скуп \(A\) а њему одговарајућа грана из скупа \(II\) се пребацује у скуп \(I\). Након тога се понавља корак 1 и процес се понавља све док се циљни чвор не пребаци у скуп \(A\).

Наредна анимација приказује примену Дајкстриног алгоритма на одређивање најкраћих путева од Суботице до осталих Војвођанских градова. Градови до којих је одређено најкраће растојање су обојени у зелено. Пошто су суседни градови релативно близу један другом, путеви између њих су скоро прави и у већини случајева дужине путева задовољавају неједнакост троугла. Стога се почетна процена дужине најкраћег пута ретко када мења. Ипак, постоји један изузетак. Дужина пута до Вршца се иницијално процењује на 227,4 km, узевши у обзир пут преко Кикинде. Касније се та вредност смањује на 213,2 km, узевши у обзир пут преко Бечеја и Зрењанина. Рецимо и да се у случају када је познато да за све гране важи неједнакост троугла Дајкстрин алгоритам може додатно оптимизовати, али се тиме нећемо бавити).

Чворови у скупу \(A\) обојени су зеленом бојом (до њих је познато најкраће растојање од почетног чвора тј. од Суботице). Бели чворови припадају скупу \(B\). Чворови из скупа \(B_1\) су они који имају коначно растојање и повезани су жутим гранама, а чворови из скупа \(B_2\) су они који имају бесконачно растојање. Гране из скупа \(I\) су обојене зеленом бојом, гране из скупа \(II\) жутом, док су одбачене гране из скупа \(III\) црвене или сиве (црвене спајају зелене и беле чворове, а сиве гране два зелена чвора). Неразмотрене гране из скупа \(III\) су означене танким, црним линијама. У анимацији се наизменично приказује стање након извршавања корака 1, па затим корака 2 и тако док се не одреде најкраћа растојања до свих градова (на првој слици је приказано убацивање почетног града у скуп \(A\), након тога се извршава корак 1 и три гране се додају у скуп \(B\), након тога се извршава корак 2 којим се Бачка Топола пребацује у скуп \(A\), а грана која је спаја са Cуботицом у скуп \(I\), након тога се понавља корак 1 који анализира гране од Бачке Тополе до њој суседних градова из скупа \(B\), након тога корак 2 у ком се Сомбор убацује у скуп \(A\) итд.).

Прикажимо сада и имплементацију Дајкстриног алгоритма у језику C#. Претпостављамо да је у питању редак граф, који представљамо коришћењем листама суседа. За сваки чвор се памти листа грана у облику уређених парова који се састоје од дужине гране (реалан број) и редног броја суседног чвора (природан број). Након учитавања графа учитавају се и редни број почетног и циљног чвора. Низ duzinaPuta садржи дужину најкраћег до тада пронађеног пута до сваког чвора (то је низ \(r_v\) из теоријског објашњења). Пошто желимо да поред дужине пута одредимо и сам најкраћи пут (тј. чворове на том путу), у помоћном низу roditelji за сваки чвор памтимо претходни чвор на најкраћем путу до њега. Тада најкраћи пут до било ког чвора можемо одредити праћењем родитеља од циља према старту и обртањем редоследа добијеног низа чворова. Чворове до којих је одређена дужина најкраћег пута (решене чворове, тј. чворове из скупа \(V_k\)) региструјемо помоћу низа логичких вредности resen. Главна петља Дајкстриног алгоритма се извршава све док циљни чвор не постане решен (или док се не реше сви чворови ако не постоји неки посебно истакнути циљни чвор). У унутрашњој петљи анализом свих чворова проналазимо онај нерешени чвор cvorMin који је тренутно најближи почетном (ако такав чвор не постоји, онда циљ није достижан). Тај чвор проглашавамо решеним (додајемо га у скуп \(V_k\)). Ако је у питању циљни чвор, алгоритам се прекида јер је одређено растојање од почетног до циљног чвора. У супротном анализирамо све суседе чвora cvorMin и ажурирамо дужине најкраћих путева до његових суседа, ако је то потребно. Након завршетка петље, коришћењем помоћног низа roditelji можемо реконструисати пут од циља до старта. Пошто нам је потребан пут од старта до циља, користимо помоћни стек да бисмо обрнули редослед чворова.

Имплементација која је приказана је елементарна, али није најефикаснија могућа. Наиме, у сваком кораку се пролазе сви чворови да би се пронашао онај нерешени чвор који је у том тренутку најближи почетном чвору. Ако је \(|V|\) број чворова графа, спољна петља се извршава \(|V|\) пута, док унутрашња петља такође увек прави \(|V|\) корака, што само по себи генерише квадратну сложеност у односу на број чворова \(|V|\). Чак иако би се у унутрашњој петљи анализирали само нерешени чворови, сложеност би остала квадратна.

Ефикасније имплементације овог алгоритма користе ред са приоритетом, у ком се чувају нерешени чворови уређени по тренутном растојању од почетног чвора, који омогућава да се најближи чвор пронађе у времену \(O(1)\). Ту се подразумева да чвор који има најмању вредност растојања има заправо највећи приоритет и да ће први бити избачен из реда. Убацивање елемената у ред са приоритетом и избацивање елемената из њега је могуће у времену \(O(\log(k))\), где је \(k\) тренутни број елемената у реду, што даје могућност да се направи имплементација чија је сложеност \(O((|E| + |V|)\log |V|)\). Заинтересоване читаоце упућујемо на Методичку збирку задатака на порталу petlja.org у ком је та имплементација детаљно описана.

Сви најкраћи путеви¶

Најкраће путеве између свих парова чворова можемо одредити тако што из сваког чвора покренемо Дајкстрин алгоритам. Уз ефикасну имплементацију Дајкстриног алгоритма у ретким графовима (код којих је број грана пре у линеарној, а не квадратној вези са бројем чворова) сложеност тог приступа је \(O(|V|^2\log(|V|)\). Међутим, у густим графовима овај приступ даје сложеност \(O(|V|^3\log(|V|)\) и тада је чак боље користити наивну имплементацију Дајкстриног алгоритма, која је сложености \(O(|V|^2)\) и која даје укупну сложеност \(O(V^3)\). У наставку ћемо видети два још једноставнија алгоритма који решавају овај проблем у сложености \(O(|V|^3)\) без обзира на број грана у графу. За разлику од Дајкстриног, ове алгоритме је могуће применити и на граф који садржи гране негативне дужине док год не садржи циклусе негативне дужине, што је још један значајан аргумент у њихову корист. Ово је заправо најопштији могући случај, јер чим граф садржи циклус негативне дужине, дужина најкраћег пута није јасно дефинисана (можемо се кретати тим циклусом и тиме произвољно смањивати дужину). Ако нема циклуса негативне дужине, најкраћи путеви не садрже циклусе (нема чворова који се понављају). Наиме, уклањање циклуса тј. дела пута од неког поновљеног чвора \(i\) до тог истог чвора \(i\) не може да повећа дужину пута, па уклањањем циклуса из путева добијају краћи путеви (или бар путеви исте дужине).

Рецимо и да свих парова чворова има \(|V|^2\), па се дужине свих најкраћих путева најбоље репрезентују матрицом димензије \(|V| \times |V|\). Ако је граф неусмерен, онда је довољно памтити само горњи (или само доњи) троугао те матрице.

Флојд-Варшалов алгоритам¶

Овај елегантан алгоритам су независно открили Роберт Флојд, Стивен Варшал, Бертран Рој, Питер Ингерман и у мало специфичном облику Стивен Клини.

Основна идеја Флојд-Варшаловог алгоритма је да се у сваком кораку \(k\) пронађу најкраћа растојања између свих парова чворова, али само преко путева који осим почетног и крајњег чвора садрже међучворове који припадају неком скупу чворова \(V_k\). Тај скуп је иницијално празан и у сваком наредном кораку се проширује неким новим чвором, све док на крају не обухвати све чворове графа (у том тренутку не постоје никаква ограничења на допуштене путеве и знамо да су пронађена тражена најкраћа растојања). Редослед додавања чворова у скуп \(V_k\) није битан и обично се чворови додају у унапред датом редоследу њихове нумерације.

Базу индукције чини следеће разматрање. Када је скуп \(V_k\) празан, путеви не смеју да садрже ниједан међу чвор, па је су допуштени само директни путеви (гране графа). To значи да се матрица свих најкраћих путева може иницијализовати матрицом тежина грана.

Опишимо сада и шта се дешава током индуктивног корака тј. приликом додавања неког чвора \(k\) скупу \(V_k = \{0, 1, \ldots, k-1\}\). Размотримо шта се дешава са најкраћим путем између нека два чвора \(i\) и \(j\). Постоје две могућности:

1. Најкраћи пут између \(i\) и \(j\) који сме да садржи чворове скупа \(V_k \cup {k}\) не садржи чвор \(k\) (он садржи само неке од чворова из скупа \(V_k = \{0, 1, \ldots, k-1\}\)).

2. Најкраћи пут између \(i\) и \(j\) који сме да садржи чворове скупа \(V_k \cup {k}\) садржи чвор \(k\). Тада се чвор \(k\) на том путу налази само једном (јер најкраћи путеви у графу без негативних циклуса не садрже поновљене чворове). Тај се пут онда разлаже на најкраћи пут од \(i\) до \(k\) и најкраћи пут од \(k\) до \(j\), при чему оба та најкраћа пута као међучворове садрже само чворове из скупа \(V_k\) и зато их на основу индуктивне хипотезе већ знамо.

Ако са \(w_{ij}\) означимо тежину гране између чворова \(i\) и \(j\), а са \(d^k(i, j)\) означимо дужину најкраћег пута између чворова \(i\) и \(j\) који користе само међучворове из скупа \(V_k = \{0, 1, \ldots, k-1\}\), тада важе следеће рекурентне везе:

\[d^0(i, j) = w_{ij}\]

\[d^{k+1}(i, j) = \min(d^k(i, j), d^k(i, k) + d^k(k, j))\]

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

❮

❯

Ова анимација је креирана коришћењем веб-апликације доступне на сајту Математичког факултета у Београду (http://www.matf.bg.ac.rs/~filip/algoritmi/flojdVarsal.html). Покушај да коришћењем ове апликације учврштиш своје разумевање рада овог алгоритма.

Имплементација алгоритма је веома једноставна и у њој се матрица најкраћих растојања ажурира у три угнежђене петље. Јако је важно нагласити да се у спољној петљи врши итерација кроз допуштене међучворове, а да се у унутрашњим петљама врши итерација кроз поља матрице (међучвор мора да буде у спољашњој петљи и ако је он означен са k, а ако су чворови између којих се ажурира пут обележени са i и j, тада редослед петљи треба да буде k-i-j, а не i-j-k).

Из ове имплементације је сасвим јасно да је сложеност овог алгоритма \(O(|V|^3)\).

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

Транзитивно затворење¶

Флојд-Варшалов алгоритам се може употребити и за проналажење транзитивног затворења релације. Подсетимо се, бинарна релација \(\rho\) на скупу \(A\) је било који подскуп \(A \times A\). Транзитивно затворење дате релације \(\rho\) је најмања релација \(\rho^+\) која садржи дату релацију (важи \(\rho \subseteq \rho^+\)), а која је транзитивна. Другим речима, потребно је постојећој релацији додати што мањи број нових уређених парова, тако да се добије транзитивна релација.

На наредој слици је графом представљена једна једноставна релација и њено транзитивно затворење. Гране које је потребно додати да би релација постала транзитивна су обојене црвеном бојом. Пошто је A у релацији са B, а B је у релацији са C, да би релација била транзитивна потребно је и да A буде у релацији са C. Слично, пошто је B у релацији са C, а C у релацији са D, мора да важи и да је B у релацији са D. На крају, пошто је након додавања гране A у релацији са C и пошто је C у релацији са D, мора да важи и да је A у релацији са D (исти закључак следи и због тога што је A у релацији са B и B у релацији са D). Након додавања три гране, релација је постала транзитивна.

У транзитивним релацијама сви достижни чворови су достижни директно, преко једне гране. Стога је за одређивање транзитивног затворења за сваки чвор потребно одредити који су чворови из њега достижни. Ово се може свести на проблем свих најкраћих путева тако што се гранама вештачки доделе дужине 1 и у тако формираном графу одреде дужине свих најкраћих путева Флојд-Варшаловим алгоритмом. Достижне чворове ћемо препознати као оне чворове код којих је најкраће растојање коначно (код недостижних чворова остаће иницијална вредност бесконачно). Можемо отићи и један корак даље - пошто нас занима само да ли постоји пут, а не и која је његова дужина, можемо формирати логичку матрицу коју ћемо иницијализовати тако што ћемо на места која одговарају чворовима који су повезани граном стављати вредност тачно, а на остала места нетачно. Пут између чворова \(i\) и \(j\) преко међучворова из скупа \(\{0, \ldots, k\}\) постоји ако и само ако постоји пут преко међучворова из скупа \(\{0, \ldots, k-1\}\) или постоји пут од \(i\) до \(k\) и од \(k\) до \(j\) преко чворова из скупа \(\{0, \ldots, k-1\}\). Тако модификована варијанта Флојд-Варшаловог алгоритма је заснована на следећим рекурентним релацијама (\(A_{ij}\) је елемент матрице повезаности, док \(t^k(i, j)\) значи да постоји пут од \(i\) до \(j\) преко чворова скупа \(\{0, \ldots, k-1\}\)).

\[t^0(i, j) = A_{ij}\]

\[t^{k+1}(i, j) = t^k(i, j) \vee (t^k(i, k) \wedge t^k(k, j))\]

Ове везе се веома се једноставно преводе у програм (опет са три угнежђене петље).