U ovom blog postu objasnit ćemo principe, primjere i stvarne primjene Dijkstrinog algoritma na lako razumljiv način.
Uvod
Prisjetite se bajke „Ivica i Marica“. Kad je njihova maćeha ostavila djecu u šumi, njihov prvi pokušaj - bacanje kamenčića kako bi im označili put - nije uspio, a njihov drugi pokušaj - ostavljanje krušnih mrvica - nije završio neuspjehom jer su ih ptice pojele. Da su tada postojale aplikacije za navigaciju ili mapiranje putem pametnih telefona, braća i sestre se ne bi izgubili, a plan njihove maćehe bi se raspao. Kao što ovaj primjer pokazuje, problem „pronalaženja najbrže rute od početne točke do odredišta“ ostao je ključna tema kroz povijest, od drevnih priča do današnje tehnologije.
Grafovi i osnovni koncepti
Da bismo razumjeli Dijkstrin algoritam, prvo moramo definirati što znači "graf" u kontekstu računarstva. Ovdje graf nije funkcionalni graf nacrtan na ravnini, već podatkovna struktura koja se sastoji od skupa vrhova i bridova koji ih spajaju. Na primjer, ako vrhove zamislimo kao stanice podzemne željeznice ili autobusne stanice, bridovi postaju željezničke pruge ili ceste koje povezuju te vrhove.
Rubovima mogu biti dodijeljene težine; te vrijednosti predstavljaju mjerljive troškove, poput udaljenosti ili vremena potrebnog za putovanje između dva vrha. Osim toga, ako rubovi imaju smjerove, graf postaje „usmjereni graf“, gdje je kretanje dopušteno samo u smjeru strelice. Dijkstrin algoritam izračunava najkraću udaljenost i put od određene početne točke do svakog drugog vrha u takvom grafu.
Kako funkcionira Dijkstrin algoritam
Objasnit ćemo algoritam koristeći uobičajeni primjer. Početna vrijednost početnog vrha postavljena je na 0, dok su početne vrijednosti svih ostalih vrhova postavljene na beskonačnost (∞), što znači da još nema informacija o povezanosti. Ove vrijednosti predstavljaju „najkraću do sada poznatu udaljenost (ili vrijeme) za dosezanje tog vrha od početne točke.“
U prvom koraku (Korak 1), započinjemo s početnim vrhom postavljenim na 0. U drugom koraku (Korak 2), za sve susjedne vrhove izravno dostupne iz početnog vrha, bilježimo privremenu vrijednost za svaki od njih dodavanjem vrijednosti početnog vrha (0) težini odgovarajućeg brida. U primjeru, te su vrijednosti zabilježene kao 8, 9 i 11. U ovom trenutku, obrada početnog vrha je završena.
„Obrađeni vrh“ odnosi se na vrh za koji se ne može pronaći kraći put, što znači da je određena njegova konačna najkraća udaljenost. U Dijkstrinom algoritmu, nakon što se na ovaj način odredi najkraća udaljenost do vrha, taj se vrh označava kao obrađen i njegova se vrijednost više nikada ne mijenja.
U trećem koraku (Korak 3), među do sada zabilježenim privremenim vrijednostima odabiremo vrh s najmanjom vrijednošću. U primjeru, odabran je vrh s vrijednošću 8. Počevši od ovog vrha, udaljenosti od početne točke do ovog vrha koriste se za ažuriranje vrijednosti okolnih vrhova. Kroz ovaj proces dolazi do ažuriranja - na primjer, nove kandidatske udaljenosti za neke susjedne vrhove izračunavaju se kao 18. Nakon što je obrada ovog vrha završena, on se također označava kao obrađen.
U četvrtom koraku (Korak 4) obrađujemo vrh sa sljedećom najmanjom vrijednošću - u ovom primjeru, onom s vrijednošću 9. I za ovaj vrh na isti način izračunavamo udaljenosti kandidata za susjedne vrhove. Tijekom ovog procesa, nove vrijednosti kandidata (npr. 15, 10, 12) mogu se pojaviti za vrhove kojima su već dodijeljene vrijednosti. Ako je nova vrijednost manja od postojeće, ona prepisuje postojeću vrijednost; inače se zadržava izvorna vrijednost. Ova operacija naziva se "relaksacija ruba" i nužan je postupak jer uvijek tražimo najkraći put.
Počevši od petog koraka (Korak 5), ista se metoda ponavlja. Svaki put se odabire vrh s najmanjom privremenom vrijednošću među onima koji još nisu obrađeni, a privremene vrijednosti susjednih vrhova ažuriraju se njihovim opuštanjem kroz susjedne bridove. Ponavljanjem ovog postupka dok se svi vrhovi ne obrade, možemo odrediti najkraće udaljenosti od početne točke do svakog vrha, kao i najkraće putove.
Primjer primjene: Mreže i usmjerivači
Računalne mreže su odličan primjer područja gdje se Dijkstrin algoritam široko koristi u praksi. Budući da bi bilo neučinkovito da milijarde uređaja budu izravno spojeni na jednu mrežu - kao što je slučaj s internetom - uređaji u neposrednoj blizini formiraju lokalne mreže, koje se zatim spajaju na mreže više razine u hijerarhijskoj strukturi. U tako složenoj strukturi povezivanja postoje bezbrojni putovi od jednog uređaja do drugog.
U mreži, svaki čvor (kao što je usmjerivač) mora procijeniti putove na temelju određenih troškova (propusnost, latencija itd.) i pronaći "najbrži" ili "najjeftiniji" put do odredišta. Usmjerivači koriste algoritme najkraćeg puta, kao što je Dijkstrin algoritam, kako bi odredili optimalni put - odnosno sljedeći skok - na koji bi trebali proslijediti promet. Međutim, budući da se uvjeti prometa u stvarnom vremenu stalno mijenjaju, praktičnije je da svaki usmjerivač pruža samo informacije o neposredno sljedećem segmentu mreže - umjesto da usmjerivač najavljuje fiksni, potpuni put - i da svaki usmjerivač ažurira te informacije u hodu kako se put konstruira.
Zaključak: Pouke iz istraživanja puta
Do sada smo ispitali osnovne koncepte Dijkstrinog algoritma, njegov postupni rad i kako se primjenjuje u mrežama. Da Ivica i Marica nisu htjeli zalutati u šumi, trebala bi im pouzdanija metoda navigacije od jednostavnih markera. Zapravo, algoritmi poput Dijkstrinog igraju sličnu ulogu kada se krećemo ili prenosimo podatke. Nadam se da ćete imati na umu ideje Dijkstrinog algoritma kako se ne biste uznemirili prilikom putovanja nepoznatim putem i kako biste mogli pronaći učinkovite rute čak i unutar složenih mreža.
