Dijkstra, ir kodėl ji teisinga

Dijkstros algoritmas remiasi vienu teiginiu.

Kodėl jis teisingas

Kai iš eilės imi pigiausią dar neapdorotą mazgą, jo atstumas jau yra galutinis.

Įrodymas telpa į sakinį. Tarkim, iki mazgo v yra pigesnis kelias, kurio dar neradome. Tas kelias turi kirsti ribą tarp apdorotų ir neapdorotų mazgų — o jo pirmasis neapdorotas mazgas u yra pigesnis už v. Vadinasi, u būtų buvęs paimtas anksčiau, ne v.

Tai neįmanoma, jei briaunos nėra neigiamos. Nes tada „toliau kelyje" reiškia „ne pigiau". Ketvirtame žingsnyje pamatysi, kas nutinka, kai šita sąlyga sulaužoma.

Palygink su keturiolikta pamoka: ten BFS sluoksniai buvo tas pats argumentas paprastesniu pavidalu. Dijkstra yra BFS, kurioje sluoksnius pakeitė kaina.

Pats algoritmas

Dijkstra(from, to):
    dist[*] ← ∞;  dist[from] ← 0
    frontier ← {from su 0}

    kol frontier netuščias:
        v, d ← PIGIAUSIAS frontier elementas        // ← visa esmė
        jei done[v]: praleisk                       // pasenęs įrašas
        done[v] ← true
        jei v = to: grąžink kelią ir d
        kiekvienai briaunai (v → w, kaina c):
            jei d + c < dist[w]:
                dist[w] ← d + c
                prev[w] ← v
                įdėk w į frontier su d + c

Palygink su keturioliktos pamokos BFS. Skiriasi trys dalykai: dist masyvas vietoj seen, sąlyga d + c < dist[w] vietoj !seen[w], ir frontier atiduoda pigiausią, o ne seniausią.

Trečiasis skirtumas yra vienintelis, kuriam reikia struktūros.

Du frontier variantai

Krūva (13 pamoka): Push ir Pop kainuoja O(log V).

Tiesinė peržiūra: jokios struktūros; kiekviename žingsnyje peržiūrimi visi V mazgai ir pasirenkamas mažiausias. O(V).

Abu teisingi ir grąžina tą patį kelią. Penktame žingsnyje pamatuosi, kiek kainuoja skirtumas.

Pasenę įrašai: kodėl krūva turi daugiau elementų nei mazgų

Radus pigesnį kelią iki w, w jau gali būti krūvoje su senesne, brangesne reikšme. Ką daryti?

Yra du atsakymai.

Sumažinti raktą (decrease-key): surasti w krūvoje ir pataisyti jo reikšmę. Bet krūva nežino, kur w yra — reikėtų atskiro indekso, atnaujinamo per kiekvieną sukeitimą. Tryliktoje pamokoje pamatavai, kad sukeitimų yra 6 922 vienam 10 000 elementų pastatymui; kiekvienas jų pabrangtų.

Tinginė šalinimas (lazy deletion): tiesiog įdėti w dar kartą. Krūvoje bus keli to paties mazgo įrašai; pirmasis ištrauktas yra pigiausias, o likusieji atpažįstami pagal done[v] ir praleidžiami.

Antrasis variantas yra tas, kurį rašo transit, ir tas, kurį rašysi tu. Kaina: krūva laiko šiek tiek daugiau, negu turi mazgų. Kiek — pamatuosi ketvirtame žingsnyje.

Kaina

V ištraukimų po O(log V), E įdėjimų po O(log V):

O((V + E) log V) su krūva. O(V² + E) su tiesine peržiūra.

Retame grafe — o tavo vidutinis laipsnis yra 1.49 — pirmasis yra beveik tiesinis, antrasis — kvadratinis.