Svoriniai grafai, Trumpiausio kelio paieška – Dijkstros algoritmas

Most of fundamental ideas of science are essentially simple.
Dauguma fundamentalių mokslo idėjų yra iš esmės paprastos.
Albertas Enšteinas (Albert Einstein)

Dažnai tikslinga grafo briaunai (arba lankui) priskirti kokį nors dydį. Pavyzdžiui, jei grafu modeliuojame vietovės žemėlapį (viršūnėmis – miestus, o briaunomis – kelius), tai briaunoms galima priskirti tų kelių ilgius. Šiame skyrelyje aptarsime tokių grafų vaizdavimą ir vieną iš garsiausių algoritmų – Dijkstros algoritmą trumpiausiam keliui rasti.

Svoriniai grafai

Svorinio grafo pavyzdys

Fig. 60 Svorinio grafo pavyzdys

Grafas, kurio visoms briaunoms (lankams) yra priskirti dydžiai (svoriai), vadinamas svoriniu. Dažniausiai nagrinėjami svoriniai grafai, kurių briaunų svoriai yra skaičiai.

Galime tarti, kad paprastas besvoris grafas tėra atskiras svorinio grafo atvejis, kai visų briaunų svoriai lygūs 1.

Duomenų struktūra, kuria galime pavaizduoti svorinį grafą, nesudėtinga. Galime naudoti kaimynystės matricą, kurioje saugosime briaunų svorius. Ta pati matrica turėtų saugoti ne tik briaunų svorius, bet ir parodyti, kurios grafo briaunos egzistuoja, kurios ne. Neegzistuojančias briaunas galime žymėti tokiu skaičiumi, kokio svorio būti negali, pavyzdžiui „begaliniu“ (labai dideliu) svoriu arba neigiamu skaičiumi (pavyzdžiui, jei grafo svoriai reiškia atstumus tarp miestų). Bet kuriuo atveju reikia būti tikram, kad jokioje algoritmo vykdymo stadijoje egzistuojančios briaunos svoris negalės įgauti tokios reikšmės.

const MAXN = ...; { maksimalus grafo viršūnių skaičius }
      BEGALINIS = MAXINT;
type grafas = record
         n : integer;      { viršūnių skaičius }
         svoris : array [1..MAXN,
                         1..MAXN] of integer;
                           { briaunų svorių matrica }
     end;

Šitaip vaizduojant grafą, viršūnes u ir v jungia briauna, jei G.svoris[u, v] < BEGALINIS.

Jei grafas vaizduojamas kaimynystės sąrašais, tai briaunos svorį tenka arba saugoti atskirame dvimačiame masyve, arba kiekvienai viršūnei sudaryti iš jos išeinančių briaunų svorių sąrašą.

Trumpiausio kelio paieškos algoritmas – Dijkstros algoritmas

Nagrinėjant olimpiadinių uždavinių sprendimus dažnai gali tekti susidurti su Dijkstros algoritmu trumpiausio kelio grafe paieškai. Šio algoritmo autorius – E. V. Dijkstra (Edsger Wybe Dijkstra) – olandų mokslininkas, daug nusipelnęs kompiuterių mokslui, ypač programavimo kalbų srityje. Trumpiausio kelio algoritmas nėra svarbiausias jo darbas, tačiau daugelis Dijkstros pavardę sieja būtent su šiuo algoritmu.

E. V. Dijsktra

Fig. 61 E. V. Dijsktra (Edsger Wybe Dijkstra) 1930–2002

Pats E. V. Dijkstra apie tai rašo: „Daug metų plačiuose sluoksniuose trumpiausio kelio algoritmas garsino mano vardą ir teikė šlovės, tačiau nuostabu tai, kad jis buvo sukurtas net be popieriaus ir pieštuko, geriant kavą su žmona saulėtoje Amsterdamo kavinės terasoje, sukurtas tik pademonstruoti kompiuterio galimybėms…“

Jau esame aptarę vieną algoritmą, tinkamą trumpiausio kelio paieškai – paiešką platyn. Pradėta viršūnėje p, paieška platyn pirmiau ima viršūnes, kurių atstumas nuo viršūnės p (matuojamas briaunų, kuriomis einama, skaičiumi) yra mažiausias.

Nagrinėkime svorinį grafą G, kurio briaunos (u, v) svoris reiškia atstumą tarp viršūnių u ir v. Kelio svoriniame grafe ilgiu vadinsime visų kelią sudarančių briaunų svorių sumą. Nagrinėsime svorinį grafą G, kurio briaunos (u, v) neneigiamas svoris reiškia atstumą tarp viršūnių u ir v. Kaip ieškoti trumpiausio kelio tokiame grafe? Nesunku įsitikinti, kad paieška platyn čia visai netinkamas algoritmas, kadangi trumpiausias kelias nebūtinai reikš mažiausią briaunų, kuriomis einama, skaičių (pavyzdžiui, pasiekti viršūnę einant dviem briaunomis, kurių svoriai atitinkamai, 1 ir 2, yra „pigiau“ negu viena briauna, kurios svoris 5, nes 1 + 2 = 3 < 5).

Dijkstros algoritmas, kaip ir paieška platyn, iš duotosios viršūnės p randa trumpiausius kelius iki visų svorinio grafo viršūnių. Algoritmas skirsto viršūnes į dvi aibes: tų, iki kurių trumpiausi keliai (ir atstumai) jau žinomi (jas vadinsime prijungtomis), ir visų kitų.

Pradžioje nežinomas trumpiausias kelias nė iki vienos viršūnės, išskyrus pradinę p, tad pažymima, kad atstumai iki šių viršūnių yra begaliniai. Atstumas (nuo pradinės) iki pradinės viršūnės jau žinomas – jis lygus nuliui.

Kiekvienu žingsniu algoritmas suranda dar neprijungtą viršūnę, iki kurios atstumas yra mažiausias (pirmu algoritmo žingsniu tai pradinė viršūnė p, kadangi iki visų kitų viršūnių atstumai yra begaliniai). Pasirinktoji viršūnė prijungiama, o tuomet atnaujinama informacija apie visas neprijungtas jos kaimynes: galbūt kelias iki šios viršūnės dar nebuvo rastas, o jei buvo – tai galbūt kelias, einantis per ką tik prijungtąją viršūnę iki šios kaimynės, yra trumpesnis už iki šiol rastąjį.

Taigi pirmuoju algoritmo žingsniu prijungiama pradinė viršūnė p. Antruoju – artimiausia p kaimynė. Kiekvienu žingsniu prijungiamų viršūnių atstumai sudaro nemažėjančią seką, kadangi visąlaik bandoma prijungti kuo artimesnes viršūnes. Šie samprotavimai intuityviai pagrindžia algoritmo teisingumą. Prijungdami viršūnę, galime būti tikri, jog rastasis atstumas yra trumpiausias, kadangi visi kiti, vėliau atrasti, trumpiausi atstumai bus tik ilgesni už šį.

Kadangi ieškoma trumpiausių kelių, o ne tik jų ilgių, kiekvienai viršūnei išsaugoma jos pirminė viršūnė (tai viršūnė, iš kurios į ją ateinama einant trumpiausiu keliu). Kol kelias iki viršūnės nerastas, jos pirminė viršūnė yra neapibrėžta. Atnaujinant atstumą iki viršūnės, kartu pažymima, iš kurios viršūnės į ją ateinama. Algoritmo vykdymo metu kiekvienos viršūnės pirminė viršūnė (kaip ir trumpiausias rastas atstumas) gali ne kartą pasikeisti. Dijkstros algoritmo vykdymas konkrečiame grafe, kai ieškomi trumpiausi keliai iš viršūnės a iki kitų grafo viršūnių.

Table 7 Dijkstros algoritmo iliustracija
Dijkstros algoritmo iliustracija Pradinė situacija: trumpiausio kelio iki viršūnės a (pasirinktosios pradinės viršūnės) ilgis lygus 0, o iki kitų viršūnių – nežinomas;
Dijkstros algoritmo iliustracija Viršūnė a turi dvi kaimynes b ir c; iki šių viršūnių rasti trumpesni keliai
Dijkstros algoritmo iliustracija Iš neprijungtų viršūnių išrenkama ta, iki kurios atstumas trumpiausias (viršūnę b); trumpesnio kelio iki b rasti negalima, ji prijungiama; peržiūrimos neprijungtos b kaimynės c ir d ir pastebima, kad iki šių abiejų viršūnių rasti trumpesni keliai per viršūnę b: iki viršūnės d kelias anksčiau nebuvo rastas, o iki viršūnės c buvo rastas tiesioginis kelias iš a; tačiau naujasis kelias per viršūnę b yra trumpesnis
Dijkstros algoritmo iliustracija  
Dijkstros algoritmo iliustracija  
Dijkstros algoritmo iliustracija Baigus vykdyti Dijkstros algoritmą visos viršūnės yra prijungtos (t. y. visos yra pasiekiamos iš pradinės viršūnės) ir žinomi trumpiausi atstumai iki jų: trumpiausio kelio iki viršūnės b ilgis lygus 3, iki c – 4, iki d – 6, iki e – 8.

Toliau pateikiamas algoritmo tekstas, tinkamas trumpiausių kelių paieškai tiek orientuotame, tiek ir neorientuotame grafe. Grafas vaizduojamas kaimynystės matrica.

type masyvas = array [1..MAXN] of longint;
     logmas = array [1..MAXN] of boolean;
procedure dijkstra(var G : grafas;
                   var atstumas, pirminė : masyvas;
                   p : integer);
var prijungta : logmas;
    v, u : integer;
    min : longint;
begin
    { įrašomos pradinės masyvų reikšmės }
    for u := 1 to G.n do begin
        atstumas[u] := BEGALINIS;
        pirminė[u] := -1;
        prijungta[u] := false;
    end;
    atstumas[p] := 0;
    v := p;
    while v <> 0 do begin
        { jei v <> 0, tai rasta viršūnė, kurią galima prijungti }
        prijungta[v] := true;
        for u := 1 to G.n do { peržiūrimos kaimynės }
            if (G.svoris[v, u] < BEGALINIS) and
               (atstumas[u] >
                   atstumas[v] + G.svoris[v, u])
            then begin { į viršūnę u verčiau eiti per v }
                atstumas[u] :=
                    atstumas[v] + G.svoris[v, u];
                pirminė[u] := v;
            end;
         { randama tolesnė kandidatė -
           dar neprijungta viršūnė su mažiausiu atstumu }
         v := 0;
         min := BEGALINIS;
         for u := 1 to G.n do
             if not prijungta[u] and
                (atstumas[u] < min)
             then begin
                 v := u;
                 min := atstumas[u];
             end;
         { jei jokia viršūnė nerasta, tai v = 0 ir ciklas nutraukiamas }
    end;
end;

Užrašytojo algoritmo sudėtingumas yra O(n^2), kur n – grafo viršūnių skaičius. Pasitelkus sudėtingesnes duomenų struktūras, Dijkstros algoritmą galima pagreitinti iki O((n + b) \log n) (čia b – grafo briaunų skaičius). Pastarasis sudėtingumas yra kur kas geresnis retuose (turinčiuose nedaug briaunų) grafuose.