maj mesec matematike

Algoritmi za najkraći put

Jedan od najpoznatijih algoritama za pronalaženje najkraćeg puta razvio je 1959. godine Edsger Dajkstra

Kako pronaći najkraći put između dve lokacije? Svakako je najlakše pronaći uputstvo preko aplikacija poput Mapquest ili GoogleMap, ali njihovi programeri su morali da razviju algoritme koji će ponuditi najpreciznije odgovore oslanjajući se, pre svega, na one koji pronalaze najmanju razdaljinu između čvorova u grafu.

Jedan od najpoznatijih algoritama ove vrste je Dijkstra algoritam, koji je 1959. godine razvio holandski informatičar Edsger Dajkstra. Ovaj algoritam u svakom ponavljanju postupka bira trenutno najbolje rešenje, što bi na kraju trebalo da dovede do ukupno najboljeg rešenja, odnosno najkraćeg puta.

U originalnoj verziji se putem ovog algoritma pronalazi najkraći put između dva čvora u grafu, ali češće se koriste varijante u kojima se jedan čvor uzima za polaznu tačku iz koje treba pronaći najkraće puteve ka svim ostalim čvorovima.

Ukoliko na mapi grada želite da pronađete najkraći put između dve tačke, ovaj algoritam prvo razdaljinu do nje same označava vrednošću 0, a zatim određuje koliko je daleka sledeća najbliža tačka i tako redom tražeći sledeći najbliži čvor sve dok ne stigne do cilja.

Slični algoritmi se ne koriste samo za traženje najbližeg puta, već i u nekim igrama poput Rubikove kocke sa najmanjim brojem pokušaja ili za traženja istih glumaca koji se pojavljuju u istim filmovima po sistemu koji se oslanja na „šest stepeni separacije“, odnosno pretpostavku da se pomoću prijatelja svojih prijatelja možete povezati sa bilo kojom osobom u najviše šest koraka.

Istražite druge tekstove:


Grb Republike Srbije
ecsite nsta eusea astc

CPN
Ulica kralja Petra 46
11000 Beograd
Republika Srbija
+381 11 24 00 260
centar@cpn.rs