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(logn)$.
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
}