V článku o prehľadávaní do širky sme sa snažili hľadať najkratšiu cestu v grafe. Presnejšie, mali sme graf s $n$ vrcholmi a $m$ hranami a snažili sme sa nájsť najmenší počet hrán na ceste z vrchola $a$ do vrchola $b$. Všimnime si však, že všetky hrany boli rovnocenné. To ale často nezodpovedá tomu, čo potrebujeme simulovať. Predstavme si, že náš graf bude predstavovať cestnú sieť Slovenska. Každý vrchol bude zastupovať jedno okresné mesto. Je potom jasné, že hrana medzi Bratislavou a Pezinkom nie je rovnocenná hrane medzi Trebišovom a Michalovcami. Ak chceme, aby bola naša cestná sieť dostatočne presná, každej hrane by sme museli priradiť aj číslo, ktoré reprezentuje jej dĺžku.
Dostávame preto problém, v ktorom vystupujú ohodnotené hrany. Každá hrana má priradené nezáporné číslo, ktoré reprezentuje jej dĺžku. Našou úlohou je opäť nájsť najkratšiu cestu medzi vrcholmi $a$ a $b$, nezaujíma nás však počet hrán, cez ktoré prejdeme, ale súčet dĺžok týchto hrán.
Algoritmus
Dijkstrov algoritmus funguje nasledovne. Počas celého výpočtu sú vrcholy rozdelené do dvoch množín. Na spracované a nespracované. O každom spracovanom vrchole poznáme dĺžku najkratšej cesty z vrchola $a$ doň. A pre každý nespracovaný vrchol si pamätáme dĺžku najkratšej cesty z $a$ doň, pričom táto cesta vedie iba cez už spracované vrcholy. Kým však pre spracované vrcholy platí, že dĺžka cesty, ktorú si pre ne pamätáme je určite najkratšia, pre nespracované vrcholy to platíť nemusí. Na začiatku sú všetky vrcholy nespracované a jedinú hodnotu, ktorou si môžeme byť istý je, že cesta z vrchola $a$ do vrchola $a$ má dĺžku 0.
Následne náš algoritmus vyberie nespracovaný vrchol, pre ktorý si aktuálne pamätáme najkratšiu cestu. Táto hodnota bude skutočne najkratšou cestou do z vrchola $a$ do tohto vrchola a preto môžeme tento vrchol označiť za spracovaný a podľa toho príslušne upraviť zvyšné hodnoty. Tento krok je podstatou fungovania Dijkstrovho algoritmu a jeho správnosť si dokážeme v ďalšej časti.
Najskôr si však vysvetlime, ako budeme upravovať naše hodnoty. Nech $x$ je vrchol, ktorý prehlásime za spracovaný a V[x] je dĺžka najkratšej cesty z vrchola $a$ do vrchola $x$. Táto zmena ovplyvní iba vrcholy, ktoré s vrcholom $x$ susedia. Pozrieme sa teda postupne na všetkých jeho susedov. Ak je jeho sused už spracovaný, nemusíme robiť nič, lebo preň už máme správnu odpoveď. Ak je však jeho sused, ktorého si označíme $y$, nespracovaný, s pridaním $x$ medzi spracované vrcholy sme mohli nájsť kratšiu cestu z $a$ do $y$, ktorá vedie cez už spracované vrcholy. Dĺžka takejto cesty je súčet V[x] a dĺžky hrany medzi $x$ a $y$. Pozrieme sa teda, či táto nová hodnota je lepšia, ako posledá hodnota, ktorú sme si pre $y$ pamätali. Ak áno, tak si zapamätáme túto novú hodnotu.
Naviac, po tom ako náš algoritmus skončí, tak budeme poznať dĺžku najkratšej cesty z vrchola $a$ do všetkých ostatných vrcholov, nie len do vrchola $b$, ktorý ak ste si všimli, sme celý čas vlastne ignorovali.
Dôkaz
Najdôležitejšie a jediné netriviálne tvrdenie našeho riešenia hovorí, že z nespracovaných vrchlov môžeme zobrať vrchol s najkratšou cestou a prehlásiť ho za spracovaný. A že táto dĺžka je skutočne dĺžkou najkratšej cesty, ktorá do neho vedie.
Majme teda nejaké spracované vrcholy a potom nespracované vrcholy, pre ktoré poznáme dĺžku najkratšej cesty vedúcej z $a$ do nich, ktorá vedie iba cez spracované vrcholy. Nech $x$ je nespracovaný vrchol, do ktorého vedie najkratšia takáto cesta a jej dĺžku si označme D[x]. My tvrdíme, že táto cesta je skutočne najktrašia možná z vrchola $a$ do vrchola $x$. Čo by muselo platiť, aby to nebola pravda?
Musela by existovať taká cesta z $a$ do $x$, ktorá je kratšia a vedie cez aspoň jeden ešte nespracovaný vrchol (lebo z tých, čo vedú cez spracované už máme najmenšiu možnosť). Takže najskôr pôjde táto cesta z vrchola $a$ po spracovaných vrchloch a potom prejde do nespracovaných a nejakým spôsobom príde až do vrchola $x$. Avšak, už tá prvá časť má dĺžku aspoň D[x]. Nech $y$ je prvý nespracovaný vrchol, ktorý takáto cesta navštívi. Je jasné, že platí $D[x] \leq D[y]$, pretože D[x] bola najkratšia z ciest do nespracovaného vrchola. A ak pôjdeme medzi vrcholmi $y$ a $x$, k tejto dĺžke iba pridáme, pretože všetky naše hrany majú nezápornú dĺžku. Preto je hodnota D[x] naozaj správna.
Toto zároveň ukazuje dôvod, prečo sme vyžadovali nezápornosť hrán. Ak by sa totiž v našom grafe nachádzali záporné hrany, táto podmienka by neplatila a celý Dijkstrov algoritmus by nebol správny. A ak vás napadne, že stačí nájsť najviac zápornú hranu a potom ku každej hrane pripočítať túto hodnotu, čím budú všetky hrany nezáporné, tak to nerobte. Nebude to totiž fungovať. Ak chcete hľadať najkratšie cesty v grafoch so zápornými hranami, musíte použiť robustnejšie algoritmy, akým je napríklad Floyd-Warshallov algoritmus.
Implementácia
Zamyslime sa, ako takéto riešenie naprogramovať. Pamätať si graf vieme pomocou poľa susedov -- pre každý vrchol si pamätáme zoznam jeho susedov a kvôli šetreniu pamäte (a tiež času) používame dynamické polia ako je napríklad vector. Následne si môžeme do našeho programu pridať dve ďalšie polia. Pole V[], v ktorom si budeme pamätať najkratšiu vzdialenosť z vrchola $a$ pre spracované vrcholy a pole D[], v ktorom si budeme pamätať najkratšiu cestu z $a$ idúcu iba cez spracované vrcholy pre všetky nespracované vrcholy.
V každom kole našeho algoritmu potom preiterujeme poľom D[], nájdeme vrchol s najmenšou hodnotou, tento vrchol prehlásime za spracovaný a upravíme hodnoty v poliach V[] a D[].
// V tomto poli si pamätáme graf ako zoznam susedov.
// V pair je prvé číslo suseda a potom dĺžka hrany do tohto suseda.
vector<vector<pair<int,int>>> G;
vector<int> D,V;
int n,m;
#define INF 2000000000
void pomala_dijkstra() {
D.resize(n, INF);
V.resize(n, INF);
int a = 0; // začiatočný vrchol
D[a] = 0;
// postupne pridávame spracované vrcholy
for (int i = 0; i < n; i++) {
// nájdeme vrchol s najmenšou vzdialenosťou
int v = 0;
for (int j = 1; j < n; j++) {
if (D[j] < D[v]) v = j;
}
if (D[v] == INF) break; // toto nastane, ak je napríklad nesúvislý
// vrchol v prehlásime za spracovaný a upravíme príslušné hodnoty
V[v] = D[v];
D[v] = INF;
for (int j = 0; j < G[v].size(); j++) {
int w = G[v][j].first, dlz = G[v][j].second; // sused vrchola v a jeho vzdialenosť
if (V[w] != INF) continue; // tento vrchol je už spracovaný
D[w] = min(D[w], V[v] + dlz);
}
}
// po skončení tejto funkcie máme v poli V[] najkratšie vzdialenosti od vrchola a
}Jediný problém, ktorý takáto implementácia má je časová zložitosť. Prejsť poľom D[] a nájsť najmenší prvok totiž zaberie čas $O(n)$. A túto operáciu musíme spraviť $n$ krát -- vždy keď prehlásim ďalší vrchol za spracovaný. Výsledná časová zložitosť takejto implementácie je teda $O(n^2)$.
My by sme to však chceli spraviť lepšie. Všimnime si však, že v každom kroku potrebujeme iba nájsť minimum z nejakej množiny čísel a toto minimum potom odstrániť. A to sú presne operácie, ktoré podporovala dátová štruktúra halda. Do tejto dátovej štruktúry sme vedeli vkladať čísla, zisťovať minimum z takto vložených čísel a takisto toto minimum odstraňovať. A to všetko s časovou zložitosťou $O(\log n)$.
Namiesto poľa D[] si budeme tieto hodnoty pamätať v halde (prioritnej fronte). Vznikne nám však problém. Pri pôvodnej implementácii sme pri úprave hodnôt prepisovali hodnoty v D[]. Do haldy sa však nevieme len tak pozrieť a upraviť číslo patriace vrcholu $y$. Tento problém však vyriešime ako správny programátori -- lenivo. Vždy keď pre vrchol $y$ vypočítame novú hodnotu, vložíme túto hodnotu (aj spolu s vrcholom $y$) do našej haldy. To znamená, že pre ten istý vrchol môže obsahovať aj viacero rôznych dĺžok ciest. To však nevadí, lebo tá najkratšia sa aj tak dostane na vrch ako prvá. A keď ju spracujeme, vrchol $y$ už bude označený ako spracovaný. Preto vždy, keď sa na vrch haldy dostane už spracovaný vrchol, túto hodnotu jednoducho zahodíme, pretože nám nič nové nepovie.
Ešte ostáva odhadnúť časovú zložitosť takéhoto riešenia. To bude zjavne záležať od toho, koľko hodnôt vložíme do našej haldy. Uvedomme si však, že každú hranu spracujeme najviac raz a za každú hranu pridáme do haldy najviac jeden prvok. To znamená, že časová zložitosť Dijkstrovho algoritmu bude $O(n + m \log m)$. Hodnota $n$ vyplýva z toho, že si na začiatku potrebujeme inicializovať niekoľko polí pre vrcholy a to bez ohľadu na to, koľko hrán má zadaný graf.
V našej implementácii nepoužívame vlastnú haldu, ale C++ prioritnú frontu priority_queue<>. Tá je síce maximová (vieme zisťovať hodnoty najväčších prvkov), vhodnou deklaráciou si ju vieme upraviť na haldu minimovú. Na tejto štruktúre potom vieme volať všetky tri základné operácie: push() (vlož prvok), pop() (vyhoď najmenší prvok) a top() (vráť hodnotu najmenšieho prvku).
// V tomto poli si pamätáme graf ako zoznam susedov.
// V pair je prvé číslo suseda a potom dĺžka hrany do tohto suseda.
vector<vector<pair<int,int>>> G;
vector<int> D,V;
int n,m;
void dijkstra_s_haldou() {
V.resize(n, -1);
int a = 0; // začiatočný vrchol
// vytvoríme si minimovú haldu, do ktorej ukladáme pair<int, int>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > D;
// treba si dať pozor, že ako prvý prvok pair musí byť vzdialenosť, aby bol na vrchu haldy
// vrchol s najmenšou vzdialenosťou
D.push({0,a});
while (!D.empty()) {
// v tejto časti vyhadzujeme vrcholy, ktoré sú už spracované
while (!D.empty() && V[D.top().second] != -1) D.pop();
if (D.empty()) break;
int v = D.top().second;
int vzd = D.top().first;
V[v] = vzd;
// prechádzame všetkých susedov
for (int i = 0; i < G[v].size(); i++) {
int w = G[v][i].first, dlz = G[v][i].second;
// ak je už sused spracovaný, netreba ho vkladať do haldy
if (V[w] != -1) continue;
D.push({vzd + dlz, w});
}
}
// po skončení tejto funkcie máme v poli V[] najkratšie vzdialenosti od vrchola a
}Čas poslednej úpravy: 28. marec 2020 14:53