admin 
„Tai puikus algoritmas“, – sakė Masačusetso technologijos instituto kompiuterių mokslininkas Erikas Demaine'as. „Tai labai greita, paprasta ir lengvai įgyvendinama.
Norėdami pritaikyti šią procedūrą praktikoje, turite nuspręsti dėl užrašų organizavimo sistemos – duomenų struktūros, informatikos kalba. Tai gali atrodyti kaip nedidelė techninė detalė, tačiau laikas, praleistas ieškant užrašų, kai reikia redaguoti ar pašalinti įrašą, gali turėti didelės įtakos bendram algoritmo vykdymo laikui.
Dijkstra dokumente buvo naudojama paprasta duomenų struktūra, kurią galima tobulinti. Vėlesniais dešimtmečiais mokslininkai sukūrė geresnių, švelniai vadinamų „krūva“, kuriuose tam tikrus daiktus rasti lengviau nei kitus. Jie naudojasi tuo, kad Dijkstra algoritmas visada turi pašalinti tik artimiausios likusios viršūnės įrašą. „Krūva iš esmės yra duomenų struktūra, leidžianti tai padaryti labai greitai“, – sakė Václav Rozhoň, Kompiuterių mokslo, dirbtinio intelekto ir technologijų instituto (INSAIT) Sofijoje, Bulgarijoje, mokslininkas.
1984 m. du kompiuterių mokslininkai sukūrė protingą krūvos dizainą, leidžiantį Dijkstros algoritmui pasiekti teorinę ribą arba „apatinę ribą“ per laiką, reikalingą vieno šaltinio trumpiausių kelių problemai išspręsti. Tam tikra prasme ši Dijkstros algoritmo versija yra geriausia įmanoma. Tai buvo paskutinis žodis apie standartinę problemos versiją beveik 40 metų. Viskas pasikeitė tik tada, kai keli tyrinėtojai atidžiau pažvelgė į tai, ką reiškia būti „geriausiu“.
Geriausias elgesys
Tyrėjai paprastai lygina algoritmus tirdami, kaip jiems sekasi blogiausiu atveju. Įsivaizduokite painiausią pasaulyje gatvių tinklelį, tada pridėkite keletą ypač gluminančių eismo modelių. Jei tokiomis ekstremaliomis aplinkybėmis primygtinai reikalaujate rasti greičiausius maršrutus, 1984 m. Dijkstros algoritmo versija yra tikrai nepralenkiama.
Tačiau tikimės, kad jūsų mieste nėra prasčiausio pasaulyje gatvių tinklo. Taigi galite paklausti: ar yra algoritmas, kuris būtų nepralenkiamas kiekviename kelių tinkle? Pirmas žingsnis siekiant atsakyti į šį klausimą yra daryti konservatyvią prielaidą, kad kiekvienas tinklas turi blogiausius srauto modelius. Tada norite, kad jūsų algoritmas rastų greičiausius kelius per bet kokį įmanomą grafiko išdėstymą, darydamas prielaidą, kad yra blogiausias įmanomas svoris. Tyrėjai šią sąlygą vadina „universaliu optimalumu“. Jei turėtumėte visuotinai optimalų algoritmą paprastesnei problemai – tiesiog patekti iš vieno grafiko taško į kitą, tai padėtų jums įveikti piko valandų srautą kiekviename pasaulio mieste.
