Algoritmi za najkraći put

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.

U saradnji sa Centrom za promociju nauke, „Danas“ predstavlja izabrane priče sa naučnopopularnog portala elementarium.cpn.rs