Dijkstros algoritmas: Skirtumas tarp puslapio versijų
Ištrintas turinys Pridėtas turinys
S wiki sintakse 3 |
S wiki sintakse 4 |
||
Eilutė 3:
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ų [[Miestas|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.
Eilutė 9:
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 ==
| |||