Dijkstros algoritmas: Skirtumas tarp puslapio versijų

 

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ę piramine(ang. heep) arba Fibonačio piraminę(ang. heep) pritaikant „Išrinkti mažiausią“ operaciją. Su dvejetaine piramine algoritmas reikalauja O((E+V)lgV) sudėtingumo, ir Fibonačio piraminė sumažina sudėtingumą iki O(E + VlgV).