Kommutatsiya va Marshrutizatsiya fanidan

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Kommutatsiya va Marshrutizatsiya fanidan

Mustaqil ish
Mavzu: Bellman-Ford algoritmi yordamida paketlarni marshrutlash .


Bajardi: 415-19 guruh talabasi
Sobirjonov O’tkirbek


Qabul qildi: Amirsaidov Ulug’bek
.

Toshkent 2023

37-variant
MARSHRUTIZATSIYA ALGORITMI : BELLMAN-FORD




5



3
1

4
3

3



4

1
2

3 1
3

2
2

6

Graf tugunlari - marshrutizatorlar. Graf yoylari - aloqa liniyalari. Aloqa liniyalari metrikalarga ega. Birinchi marshrutizatordan boshqa marshrutizatorlarga boladigan optimal yo`lni aniqlash kerak

1. 
   h=0. Birinchi tugunga 0 metkasini boshqa tugunlarga ∞ metkasini qo`yamiz
   

2. 
   h=1. Birinchi tugundan qadami 1 bo`lgan tugunlar metkasini o`zgartiramiz, bular 2 (1-2), 3 (1-3) tugunlar
   

3. 
   h=2. Birinchi tugundan qadami 2 bo`lgan tugunlar metkasini o`zgartiramiz, bular 2(1-3-2), 3(1-2-3), 4 (1-2-4), 5 (1-3-5) va 6 (1-2-6) tugunlar
   

4. 
   h=3. Birinchi tugundan qadami 3 bo`lgan tugunlar metkasini o`zgartiramiz, bular 4(1-3-2-4), 5(1-2-3-5), 6 (1-2-4-6) tugunlar.
   

5. 
   h=4. Birinchi tugundan qadami 4 bo`lgan tugunlar metkasini o`zgartiramiz, bular 5(1-2-4-3-5) 6(1-3-2-4-6) tugunlar.
   

Endi jadval tuzamiz

h	Lh(2)	Yo`l	Lh(3)	Yo`l	Lh(4)	Yo`l	Lh(5)	Yo`l	Lh(6)	Yo`l
0	∞	--	∞	--	∞	--	∞	--	∞	--
1	3	1-2	4	1-3	∞	1-4	∞	--	∞	--
2	3	1-2	4	1-3	4	1-2-4	5	1-3-5	5	1-2-6
3	3	1-2	4	1-3	4	1-2-4	5	1-3-5	5	1-2-6
4	3	1-2	4	1-3	4	1-2-4	5	1-3-5	5	1-2-6