"teeosas" - 1 õppematerjal

Arvutivõrgud eksami vastused

Nende kohta me teadme kanali väärtust. Kui tippude vahel on rohkem sõlmi kui üks, siis nende jaoks me ütleme, et see tee väärtus on lõpmatult suur. Tuleb otsida välja minimaalne tee. Naabrid annav oma informatsiooni, mina panen juurde teepikkuse naabriteni ja leian minimaalse. Algoritm töötab nii, et kui toimub lokaalse kanali väärtuse muutus või tuleb naabri käest informatsioon, et midagi on muutunud teede väärtuses, siis arvutatakse tabelit uuesti ümber. Kui mingis teeosas tekib muudatus, siis sellest informeeritakse omakorda naabreid. Nii see info mööda võrku läbi naabrite laiali levib, kuni kõik on saanud oma tabelid ära uuendatud. Näide: Tegemist on väikse võrguga. x->x=0 ja x->y=2 ja x->z=7 (x rohkem ei tea midagi ja see on lähtepunkt) y->y=0 ja y->x=2 ja y->z=1 z->z= 0 ja z->x=7 ja z->y=1 See info saadetakse naabritele. Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2