Dijkstros algoritmas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Animacija, vaizduojanti Deikstros algoritmo veikimą

Dijkstros algoritmas arba Deikstros algoritmasEdgar Dijkstra sukurtas algoritmas randantis trumpiausius kelius nuo vienos viršūnės iki kitų svoriniame grafe su neneigiamais svoriais.

Pavyzdžiui, jei grafo viršūnės vaizduoja miestus ir kraštinių svoriai vaizduoja atstumą tarp tų miestų, sujungtą tiesioginiu keliu, Dijkstra algoritmas naudojamas surasti trumpiausius kelius tarp tų miestų.

Algoritmo pradiniai duomenys yra kryptinis grafas G su kraštinių svoriais ir šaltinių viršūne S grafe G. Mes pavadinsime V visų viršūnių rinkinį grafe G. Kiekviena grafo kraštinė yra sutvarkyta viršūnių pora (u, v), parodanti ryšį tarp viršūnių u ir v. Visų kraštinių rinkinys yra E. Kraštinių svoriai yra užduodami pagal svorių funkciją w:E; čia u(u, v) yra ne neigiama kaina tiesiogiai einant nuo viršūnės U iki viršūnės V. Kraštinės kaina yra laikoma atstumu tarp šitų dviejų viršūnių. Kelio kaina tarp dviejų viršūnių yra kraštinių kainų suma tame kelyje.

Duotai porai viršūnių s ir t visų viršūnių rinkinyje V algoritmas suranda kelią nuo s į t su mažiausia kaina (trumpiausias kelias). Jis taip pat gali būti naudojamas rasti trumpiausių kelių kainai nuo vienos viršūnės s iki kitų viršūnių grafe.

Algoritmas dirba surasdamas kiekvienai viršūnei trumpiausio kelio kainą d[v] rastą tame kelyje tarp s ir v. Iš pradžių ši vertė yra 0 šaltinio viršūnei s (d[s]=0) ir begalybė kitoms viršūnėms, pripažįstant faktą, kad mes nežinome jokių kelių iki tų viršūnių (d[v]=∞ kiekvienam v iš V, išskyrus s). Kai algoritmas baigsis, d[v] bus trumpiausias kelias nuo s iki v, ar begalybė, jei toks kelias neegzistuoja.

Pagrindinė Djikstros algoritmo operacija yra kraštinių atlaisvinimas, jei yra kraštinė nuo u iki v, tai trumpiausias žinomas kelias nuo s iki u (d[u]) gali būti išplėstas į kelią nuo s iki v, pridedant kraštinę (u, v) prie galo. Toks kelias turės ilgį d [u]+w(u, v). Jei tai yra mažiau negu esamas d[v], mes galime pakeisti esamą vertę d[v] nauja verte. Kraštinių atlaisvinimas yra taikomas, kol visos vertės d[v] atitinka trumpiausio kelio kainą nuo s iki v. Algoritmas yra organizuojamas taip, kad kiekviena kraštinė yra atlaisvinama tik vieną kartą, kai d[u] pasiekia savo galutinę vertę.

Algoritmo sudėtingumas[taisyti | redaguoti kodą]

Paprasčiausias Djikstros algoritmo įvykdymas laiko rinkinio Q viršūnes paprastame tiesiniame sąraše ar masyve, ir operacija Išrinkti mažiausią yra paprasta tiesinė paieška per visas viršūnes Q. Šiuo atveju algoritmo sudėtingumas yra O(V^2).

Retiems grafams, tai yra grafams su mažiau nei V^2 kraštinių, Dijkstros algoritmas gali būti pritaikytas žymiai efektyviau, tai yra laikant grafą kaimyniniuose sąrašuose ir naudojant dvejetainę piramidę (angl. heap) arba Fibonačio piramidę pritaikant „Išrinkti mažiausią“ operaciją. Su dvejetaine piramide algoritmas reikalauja O((E+V)lgV) sudėtingumo, ir Fibonačio piramidė sumažina sudėtingumą iki O(E + VlgV).

Kintamieji:[taisyti | redaguoti kodą]

S – pradžios viršūnė
F – aplankytų viršūnių sąrašas
G – grafas
E – briauna su viršūnėmis (v1,v2)
V – viršūnė
dist(i) – atstumų nuo S iki kiekvienos V masyvas
prev(i) – rodyklės į ankstesnes V
i – indeksas
U – neaplankytų viršūnių sąrašas

Pseudokodas:[taisyti | redaguoti kodą]

FOR i=0 to |V|-1
        dist(i)=INFINITY
        prev(i)=NULL
END FOR

WHILE F nepilnas
        imame viršūnę v iš U su artimiausiu keliu iki S
        pridedame V į F
        FOR V briaunai(v1,v2)
                IF (dist(v1)+ilgis(v1,v2) < dist(v2)
                        dist(v2)=dist(v1)+ilgis(v1,v2)
                        prev(v2)=v1
                        [galbūt reikia atnaujinti U]
                END IF
        END FOR
END WHILE

Išorinės nuorodos[taisyti | redaguoti kodą]

Commons-logo.svg Vikiteka: Dijkstros algoritmas – vaizdinė ir garsinė medžiaga

Vikiteka