b'\n_START_ARTICLE_\nDijkstros algoritmas\n_START_PARAGRAPH_\nDijkstros algoritmas arba Deikstros algoritmas \xe2\x80\x93 Edgar Dijkstra sukurtas algoritmas randantis trumpiausius kelius nuo vienos vir\xc5\xa1\xc5\xabn\xc4\x97s iki kit\xc5\xb3 svoriniame grafe su neneigiamais svoriais._NEWLINE_Pavyzd\xc5\xbeiui, jei grafo vir\xc5\xa1\xc5\xabn\xc4\x97s vaizduoja miestus ir kra\xc5\xa1tini\xc5\xb3 svoriai vaizduoja atstum\xc4\x85 tarp t\xc5\xb3 miest\xc5\xb3, sujungt\xc4\x85 tiesioginiu keliu, Dijkstra algoritmas naudojamas surasti trumpiausius kelius tarp t\xc5\xb3 miest\xc5\xb3._NEWLINE_Algoritmo pradiniai duomenys yra kryptinis grafas G su kra\xc5\xa1tini\xc5\xb3 svoriais ir \xc5\xa1altini\xc5\xb3 vir\xc5\xa1\xc5\xabne S grafe G. Mes pavadinsime V vis\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 rinkin\xc4\xaf grafe G. Kiekviena grafo kra\xc5\xa1tin\xc4\x97 yra sutvarkyta vir\xc5\xa1\xc5\xabni\xc5\xb3 pora (u, v), parodanti ry\xc5\xa1\xc4\xaf tarp vir\xc5\xa1\xc5\xabni\xc5\xb3 u ir v. Vis\xc5\xb3 kra\xc5\xa1tini\xc5\xb3 rinkinys yra E. Kra\xc5\xa1tini\xc5\xb3 svoriai yra u\xc5\xbeduodami pagal svori\xc5\xb3 funkcij\xc4\x85 w:E; \xc4\x8dia u(u, v) yra ne neigiama kaina tiesiogiai einant nuo vir\xc5\xa1\xc5\xabn\xc4\x97s U iki vir\xc5\xa1\xc5\xabn\xc4\x97s V. Kra\xc5\xa1tin\xc4\x97s kaina yra laikoma atstumu tarp \xc5\xa1it\xc5\xb3 dviej\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3. Kelio kaina tarp dviej\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 yra kra\xc5\xa1tini\xc5\xb3 kain\xc5\xb3 suma tame kelyje._NEWLINE_Duotai porai vir\xc5\xa1\xc5\xabni\xc5\xb3 s ir t vis\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 rinkinyje V algoritmas suranda keli\xc4\x85 nuo s \xc4\xaf t su ma\xc5\xbeiausia kaina (trumpiausias kelias). Jis taip pat gali b\xc5\xabti naudojamas rasti trumpiausi\xc5\xb3 keli\xc5\xb3 kainai nuo vienos vir\xc5\xa1\xc5\xabn\xc4\x97s s iki kit\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 grafe._NEWLINE_Algoritmas dirba surasdamas kiekvienai vir\xc5\xa1\xc5\xabnei trumpiausio kelio kain\xc4\x85 d[v] rast\xc4\x85 tame kelyje tarp s ir v. I\xc5\xa1 prad\xc5\xbei\xc5\xb3 \xc5\xa1i vert\xc4\x97 yra 0 \xc5\xa1altinio vir\xc5\xa1\xc5\xabnei s (d[s]=0) ir begalyb\xc4\x97 kitoms vir\xc5\xa1\xc5\xabn\xc4\x97ms, pripa\xc5\xbe\xc4\xafstant fakt\xc4\x85, kad mes ne\xc5\xbeinome joki\xc5\xb3 keli\xc5\xb3 iki t\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 (d[v]=\xe2\x88\x9e kiekvienam v i\xc5\xa1 V, i\xc5\xa1skyrus s). Kai algoritmas baigsis, d[v] bus trumpiausias kelias nuo s iki v, ar begalyb\xc4\x97, jei toks kelias neegzistuoja._NEWLINE_Pagrindin\xc4\x97 Dijkstros algoritmo operacija yra kra\xc5\xa1tini\xc5\xb3 atlaisvinimas, jei yra kra\xc5\xa1tin\xc4\x97 nuo u iki v, tai trumpiausias \xc5\xbeinomas kelias nuo s iki u (d[u]) gali b\xc5\xabti i\xc5\xa1pl\xc4\x97stas \xc4\xaf keli\xc4\x85 nuo s iki v, pridedant kra\xc5\xa1tin\xc4\x99 (u, v) prie galo. Toks kelias tur\xc4\x97s ilg\xc4\xaf d [u]+w(u, v). Jei tai yra ma\xc5\xbeiau negu esamas d[v], mes galime pakeisti esam\xc4\x85 vert\xc4\x99 d[v] nauja verte. Kra\xc5\xa1tini\xc5\xb3 atlaisvinimas yra taikomas, kol visos vert\xc4\x97s d[v] atitinka trumpiausio kelio kain\xc4\x85 nuo s iki v. Algoritmas yra organizuojamas taip, kad kiekviena kra\xc5\xa1tin\xc4\x97 yra atlaisvinama tik vien\xc4\x85 kart\xc4\x85, kai d[u] pasiekia savo galutin\xc4\x99 vert\xc4\x99.\n_START_SECTION_\nAlgoritmo sud\xc4\x97tingumas\n_START_PARAGRAPH_\nPapras\xc4\x8diausias Djikstros algoritmo \xc4\xafvykdymas laiko rinkinio Q vir\xc5\xa1\xc5\xabnes paprastame tiesiniame s\xc4\x85ra\xc5\xa1e ar masyve, ir operacija I\xc5\xa1rinkti ma\xc5\xbeiausi\xc4\x85 yra paprasta tiesin\xc4\x97 paie\xc5\xa1ka per visas vir\xc5\xa1\xc5\xabnes Q. \xc5\xa0iuo atveju algoritmo sud\xc4\x97tingumas yra ._NEWLINE_Retiems grafams, tai yra grafams su ma\xc5\xbeiau nei  kra\xc5\xa1tini\xc5\xb3, Dijkstros algoritmas gali b\xc5\xabti pritaikytas \xc5\xbeymiai efektyviau, tai yra laikant graf\xc4\x85 kaimyniniuose s\xc4\x85ra\xc5\xa1uose ir naudojant dvejetain\xc4\x99 piramid\xc4\x99 (angl. heap) arba Fibona\xc4\x8dio piramid\xc4\x99 pritaikant \xe2\x80\x9eI\xc5\xa1rinkti ma\xc5\xbeiausi\xc4\x85\xe2\x80\x9c operacij\xc4\x85. Su dvejetaine piramide algoritmas reikalauja O((E+V)lgV) sud\xc4\x97tingumo, ir Fibona\xc4\x8dio piramid\xc4\x97 suma\xc5\xbeina sud\xc4\x97tingum\xc4\x85 iki O(E + VlgV).\n_START_SECTION_\nKintamieji:\n_START_PARAGRAPH_\nS \xe2\x80\x93 prad\xc5\xbeios vir\xc5\xa1\xc5\xabn\xc4\x97_NEWLINE_F \xe2\x80\x93 aplankyt\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 s\xc4\x85ra\xc5\xa1as_NEWLINE_G \xe2\x80\x93 grafas_NEWLINE_E \xe2\x80\x93 briauna su vir\xc5\xa1\xc5\xabn\xc4\x97mis (v1,v2)_NEWLINE_V \xe2\x80\x93 vir\xc5\xa1\xc5\xabn\xc4\x97_NEWLINE_dist(i) \xe2\x80\x93 atstum\xc5\xb3 nuo S iki kiekvienos V masyvas_NEWLINE_prev(i) \xe2\x80\x93 rodykl\xc4\x97s \xc4\xaf ankstesnes V_NEWLINE_i \xe2\x80\x93 indeksas_NEWLINE_U \xe2\x80\x93 neaplankyt\xc5\xb3 vir\xc5\xa1\xc5\xabni\xc5\xb3 s\xc4\x85ra\xc5\xa1as\n_START_SECTION_\nPseudokodas:\n_START_PARAGRAPH_\nFOR i=0 to |V|-1_NEWLINE_dist(i)=INFINITY_NEWLINE_prev(i)=NULL_NEWLINE_END FOR_NEWLINE__NEWLINE_WHILE F nepilnas_NEWLINE_imame vir\xc5\xa1\xc5\xabn\xc4\x99 v i\xc5\xa1 U su artimiausiu keliu iki S_NEWLINE_pridedame V \xc4\xaf F_NEWLINE_FOR V briaunai(v1,v2)_NEWLINE_IF (dist(v1)+ilgis(v1,v2) < dist(v2)_NEWLINE_dist(v2)=dist(v1)+ilgis(v1,v2)_NEWLINE_prev(v2)=v1_NEWLINE_[galb\xc5\xabt reikia atnaujinti U]_NEWLINE_END IF_NEWLINE_END FOR_NEWLINE_END WHILE'