Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Dijkstros algoritmas arba Deikstros algoritmas sukurtas algoritmas randantis trumpiausius kelius nuo vienos viršūnės iki
Dijkstros algoritmas
Dijkstros algoritmas arba Deikstros algoritmas – 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ė Dijkstros 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
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 .
Retiems grafams, tai yra grafams su mažiau nei 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:
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:
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
Nuorodos
- MIT paskaitos apie Deikstros algoritmą vaizdo įrašas
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Dijkstros algoritmas, Kas yra Dijkstros algoritmas? Ką reiškia Dijkstros algoritmas?
Dijkstros algoritmas arba Deikstros algoritmas sukurtas algoritmas randantis trumpiausius kelius nuo vienos virsunes iki kitu svoriniame grafe su neneigiamais svoriais Animacija vaizduojanti Deikstros algoritmo veikima Pavyzdziui jei grafo virsunes vaizduoja miestus ir krastiniu svoriai vaizduoja atstuma tarp tu miestu sujungta tiesioginiu keliu Dijkstra algoritmas naudojamas surasti trumpiausius kelius tarp tu miestu Algoritmo pradiniai duomenys yra kryptinis grafas G su krastiniu svoriais ir saltiniu virsune S grafe G Mes pavadinsime V visu virsuniu rinkinį grafe G Kiekviena grafo krastine yra sutvarkyta virsuniu pora u v parodanti rysį tarp virsuniu u ir v Visu krastiniu rinkinys yra E Krastiniu svoriai yra uzduodami pagal svoriu funkcija w E cia u u v yra ne neigiama kaina tiesiogiai einant nuo virsunes U iki virsunes V Krastines kaina yra laikoma atstumu tarp situ dvieju virsuniu Kelio kaina tarp dvieju virsuniu yra krastiniu kainu suma tame kelyje Duotai porai virsuniu s ir t visu virsuniu rinkinyje V algoritmas suranda kelia nuo s į t su maziausia kaina trumpiausias kelias Jis taip pat gali buti naudojamas rasti trumpiausiu keliu kainai nuo vienos virsunes s iki kitu virsuniu grafe Algoritmas dirba surasdamas kiekvienai virsunei trumpiausio kelio kaina d v rasta tame kelyje tarp s ir v Is pradziu si verte yra 0 saltinio virsunei s d s 0 ir begalybe kitoms virsunems pripazįstant fakta kad mes nezinome jokiu keliu iki tu virsuniu d v kiekvienam v is V isskyrus s Kai algoritmas baigsis d v bus trumpiausias kelias nuo s iki v ar begalybe jei toks kelias neegzistuoja Pagrindine Dijkstros algoritmo operacija yra krastiniu atlaisvinimas jei yra krastine nuo u iki v tai trumpiausias zinomas kelias nuo s iki u d u gali buti isplestas į kelia nuo s iki v pridedant krastine u v prie galo Toks kelias tures ilgį d u w u v Jei tai yra maziau negu esamas d v mes galime pakeisti esama verte d v nauja verte Krastiniu atlaisvinimas yra taikomas kol visos vertes d v atitinka trumpiausio kelio kaina nuo s iki v Algoritmas yra organizuojamas taip kad kiekviena krastine yra atlaisvinama tik viena karta kai d u pasiekia savo galutine verte Algoritmo sudetingumasPaprasciausias Djikstros algoritmo įvykdymas laiko rinkinio Q virsunes paprastame tiesiniame sarase ar masyve ir operacija Isrinkti maziausia yra paprasta tiesine paieska per visas virsunes Q Siuo atveju algoritmo sudetingumas yra O V2 displaystyle O V 2 Retiems grafams tai yra grafams su maziau nei V2 displaystyle V 2 krastiniu Dijkstros algoritmas gali buti pritaikytas zymiai efektyviau tai yra laikant grafa kaimyniniuose sarasuose ir naudojant dvejetaine piramide angl heap arba Fibonacio piramide pritaikant Isrinkti maziausia operacija Su dvejetaine piramide algoritmas reikalauja O E V lgV sudetingumo ir Fibonacio piramide sumazina sudetinguma iki O E VlgV Kintamieji S pradzios virsune F aplankytu virsuniu sarasas G grafas E briauna su virsunemis v1 v2 V virsune dist i atstumu nuo S iki kiekvienos V masyvas prev i rodykles į ankstesnes V i indeksas U neaplankytu virsuniu sarasasPseudokodas FOR i 0 to V 1 dist i INFINITY prev i NULL END FOR WHILE F nepilnas imame virsune v is U su artimiausiu keliu iki S pridedame V į F FOR V briaunai v1 v2 IF dist v1 ilgis v1 v2 lt dist v2 dist v2 dist v1 ilgis v1 v2 prev v2 v1 galbut reikia atnaujinti U END IF END FOR END WHILENuorodosVikiteka Dijkstros algoritmas vaizdine ir garsine medziagaMIT paskaitos apie Deikstros algoritma vaizdo įrasas