Matematikos moksle ir kompiuterių moksle yraatskira kryptis, vadinama grafų teorija. Savo sistemoje kyla ir išspręstos įvairios problemos, pavyzdžiui, ieškant trumpiausio kelio tarp viršūnių. Vienas iš labiausiai paplitusių būdų, kaip matematikai išspręsti šią problemą, jau seniai buvo Dijkstra algoritmas.
Manoma, kad grafiko koncepcija buvo įvesta 2008 mXVIII a. kasdienį gyvenimą. Jis išreiškė vieno iš klasikinių šios teorijos problemų - septynių Koenigsbergo tiltų - formulavimą ir sprendimą. Siekiant paaiškinti šios teorijos tikslą, dažniausiai naudojama ši analogija, kaip judėjimas tarp skirtingų miestų. Tada plokštumoje esantis grafikas parodys visą maršruto žemėlapį, kuriame viršūnės bus konkretūs taškai (pavyzdžiui, miestai), o kraštai bus keliai iš vieno viršūnės į kitą (analogiški keliui tarp miestų). Dijkstra algoritmas, be kitų metodų, gali išspręsti šį klausimą.
Viena iš standartinių grafų teorijos problemų yravienas, kuriame reikia nustatyti ekonomiškai efektyvų kelią tarp dviejų taškų. Jį plokštumoje galima sumažinti iki grafiko sprendimo, kuriame viršūnės - miestai - sujungiami kraštais, kurie yra galimi keliai. Be to, kiekvienas kelias turi savo ilgį, todėl tam tikros lėšos turės būti išleistos kelionei juo. Ši suma prilygsta briaunos svoriui grafike. Tada praktikoje problemą galima suformuluoti taip: kaip nutiesti kelią iš vieno miesto į kitą, kad kelyje būtų galima išleisti minimalius pinigus.
Sprendimai
Norėdami išspręsti šią problemą, kai kuriealgoritmai, kurie tapo plačiai žinomi mokslo pasaulyje. Pavyzdžiui, „Floyd-Warshall“, „Ford-Bellman“ algoritmas. Dijkstros algoritmas taip pat yra klasikinis būdas rasti sprendimą. Jis gali būti naudojamas tiek svertiniam (kiekvieno krašto svoris žinomas), tiek negausiam grafikui. Norėdami rasti galutinį kelią, turite pereiti kelis žingsnius.
Dijkstros algoritmas
Šio metodo esmė yra tapereinamos visos viršūnės, pradedant duota, ir kiekvienai priskiriama etiketė su tam tikra verte. Tada į rezultatą bus įtrauktos tos viršūnės, kurių etiketės yra minimalios. Pirmame etape pradinei viršūnei priskiriama etiketė, kurios vertė 0. Tada atsižvelgiama į visas šias viršūnes, tai yra tas, kurias galima pasiekti iš originalo. Jiems priskiriamos etiketės, kurių vertė nustatoma kaip šaltinio ir kelio svorio suma. Iš kito žingsnio viršūnių pasirenkama mažiausia etiketės reikšmė ir tiriamos visos viršūnės, kurias galima pasiekti iš jo nenaudojant tarpinių viršūnių. Nustatoma nauja etiketės vertė, lygi šaltinio viršūnės etiketei ir kelio svoriui. Jei gauta vertė yra mažesnė nei viršūnės etiketė, tada etiketė pakeičiama. Priešingu atveju išlieka pradinė vertė. Tokiu atveju optimizavimo rezultatas įrašomas į atskirą masyvą, kurio matmuo yra lygus grafo viršūnių skaičiui, o kelią lemia šis rezultatas. Norėdami įdiegti tokį metodą kaip „Dijkstra“ algoritmas, „Pascal“ siūlo labai patogius įrankius. Algoritmas turi pranašumą, kad jį galima lengvai naudoti kaip pagrindą programai, kuri yra mažo dydžio. Tokių programinės įrangos produktų pavyzdžių lengva rasti internete.
