Proverite svoje razumevanje Dajkstrinog algoritma tako što ćete
popuniti tablicu koja sadrži stanje niza najkraćih rastojanja od
čvora 0 u svakoj iteraciji izvršavanja algoritma (vrednost ∞
možete ili da kopirate ili da ta polja ostavite prazna). U
svakoj iteraciju se bira najbliži čvor (ako ima više čvorova na
istom rastojanju, bira se onaj sa manjim slovom). Kada popunite
tablicu proverite svoje rešenja. Polja koja su tačno popunjena
će biti uokvirena zelenom
bojom ⬤, a koja su netačno
popunjena biće uokvirena crvenom
bojom ⬤.
Prikaz rešenja
Uz svaki čvor prikazana je trenutna procena vrednosti
rastojanja od početnog čvora (to je najmanje rastojanje
putevima koji prolaze samo preko obrađenih grana). Iste
vrednosti su upisane i u odgovarajuću vrstu tabele.
U koraku k, je poznat skup koji sadrži k najbližih čvorova
početnom čvoru. Ti čvorovi grafa su obeleženi zelenom
bojom ⬤. Poznata su i
najkraća rastojanja do njih i u tabeli su prikazana
išrafirano .
Tom skupu se u svakom koraku dodaje novi čvor. Njegovo
rastojanje (najmanje od svih rastojanja do čvorova van tog
skupa) je u tabeli označeno bold fontom.
Nakon obrade novog čvora obrađuju se sve grane koje vode od
njega i ažuriraju se rastojanja do krajnjih čvorova tih
grana. Ako se rastojanje smanjilo, novo rastojanje se
prikazuje zelenom bojom ⬤,
a ako nije, prikazuje se crvenom
bojom ⬤.
Sve grane koje su obrađene su obojene crvenom
bojom ⬤. Grane preko kojih se
postiže najkraće rastojanje su obojene plavom
bojom ⬤. One određuju drvo
najkraćih puteva (najkraći put je jedinstveni put od
početnog do krajnjeg čvora u tom drvetu).