16:33, 30 rugsėjo 2007 versija taisyti Loveless (aptarimas \| indėlis) Botai 15 272 keitimai S robotas Pridedama: hu:Dijkstra-algoritmus ← Prieš tai darytas keitimas		12:08, 17 lapkričio 2007 versija taisyti anuliuoti MBIK (aptarimas \| indėlis) 41 keitimas Nėra keitimo santraukos Kitas pakeitimas →
Eilutė 5: 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]= ~~begalybė~~∞ 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ę. Eilutė 14: 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 <math>O(V^2)</math>. Retiems grafams, tai yra grafams su mažiau nei <math>V^2</math> kraštinių, Dijkstros algoritmas gali būti pritaikytas žymiai efektyviau, tai yra laikant grafą kaimyniniuose sąrašuose ir naudojant dvejetainę piramidę (ang. ''heap'') arba Fibonačio piraminę pritaikant „Išrinkti mažiausią“ operaciją. Su dvejetaine ~~piramine~~piramide algoritmas reikalauja O((E+V)lgV) sudėtingumo, ir Fibonačio ~~piraminė~~piramidė sumažina sudėtingumą iki O(E + VlgV). == Kintamieji: == Eilutė 24: V – viršūnė dist(i) – atstumų nuo S iki kiekvienos V masyvas prev(i) – ~~pointeris~~rodyklės į ankstesnes V i – indeksas U – neaplankytų viršūnių sąrašas

Dijkstros algoritmas: Skirtumas tarp puslapio versijų