Pripreme za algoritme(16)

Traženje najkraćeg puta od zadane točke- (Dijkstrin algoritam)

Ovaj algoritam nam pomaže odrediti najkraću udaljenost svake točke u grafu od referentne.
Graf opisujemo matricom veza kao i prije samo što u matricu spremamo udaljenost između točaka. Matrica udalj [N,N] gdje je N broj točaka (čvorova).
Obično koristimo barem još jedan niz u kojem označavamo one točke koje smo već uključili bio[N]

Isto tako koristimo polje u kojem za svaku točku zapisujemo do tada najkraći izračunati put d[N].
Sve dok neku udaljenost nismo izračunavali ona je negativna (d[i] = -1)

1. korak: referentni čvor je 1 (na slici označen plavom bojom)
2. korak: tražimo sve čvorove koji imaju vezu s referentnim. Njihove udaljenosti postaju d[i] = udalj[i,1]
3. korak: tražimo čvorove koji nismo prethodno obilježili, a ima najkraću vezu s referentnim čvorom (u našem slučaju to je čvor 2 — označimo ga)
3. korak: tražimo sve čvorove koji imaju izravnu vezu s označenim
4. korak: za sve čvorove kojima do tog trenutka nismo izračunavali udaljenost:
udaljenost označenog od referentnog + udaljenost nađenog od označenog
5. korak: za sve čvorovi koji imaju udaljenost d[i]>-1 provjeravamo: d(nađenog preko označenog) < d(nađenog od referentnog)
ili
d[i]+d[ref]<d[i,ref] (znači preko označenog čvora put je kraći nego prije izračunati)
6. korak: ako je istina izračunava se nova udaljenost preko označenog čvora
od 3. do 6. koraka ponavljamo dok ne prođemo sve čvorove (pretraga se ponavlja za sve čvorove koje nismo označil)

Dijkstra - kod

 Evo toliko od nas za danas. Ostalo je još 1 lekcija iz grafova. A mi Vas i dalje polako pripremamo za Infokup 2013.