|
Bellman-ford algoritmi asosida paketlarni marshrutlash
|
| Sana | 17.12.2023 | | Hajmi | 1,13 Mb. | | #121900 |
Bog'liq 1700074366 (8)|
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI.
KOMPYUTER TARMOQLARI fanidan tayyorlagan
MUSTAQIL ISHI
NKW015 guruh talabasi: Nabijonov Hamidjon.
Fan o’qituvchisi: Qodirov Azamat.
TOSHKENT 2023
BELLMAN-FORD ALGORITMI ASOSIDA PAKETLARNI
MARSHRUTLASH
Bellman-Ford algoritmı, aloqa tarmoqida eng yaroqli yo'l topish uchun ishlatiladigan algoritm. Bu algoritm graf (uchlarni aloqa tarmoqini ifodalovchi tuzilmalar) bo'yicha kamida bir boshlang'ich nuqta bilan boshlanadi va barcha uchlarga boradigan barcha yo'llarni tekshiradi. Algoritm har bir uch uchun eng qisqa yo'l vaqtinchaliklarini topadi. Agar aloqa tarmoqida salbiy tsikllar bo'lsa (misol: manbasiz qo'yishlar), algoritm xatoliklarni aniqlay oladi.
Bellman-Ford algoritmida har bir takrorlashda, barcha uchlar uchun yo'llar yangilanadi, va bu takrorlashlar vertexlar soni qadar davom etadi. Agar yo'l topilsa, algoritm yangi qiymatlarni saqlab qo'yadi.
Bu algoritm negativ og'irli qiymatlar va tsikllarni aniqlashda foydalanish uchun ham ishlatiladi.
Grafik qurilishi
C++ yordamida Belman-Ford algoritmidan foydalanib, eng qisqa yo'llarni topish
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 7
int main()
{
int a[SIZE][SIZE];
int d[SIZE];
int v[SIZE];
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
for (int i = 0; i{
a[i][i] = 0;
for (int j = i + 1; jprintf("Masofani kiriting %d - %d: ", i + 1, j + 1);
scanf("%d", &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
for (int i = 0; i{
for (int j = 0; jprintf("%5d ", a[i][j]);
printf("\n");
}
for (int i = 0; i{
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
do {
minindex = 10000;
min = 10000;
for (int i = 0; i{
if ((v[i] == 1) && (d[i]{
min = d[i];
minindex = i;
}
}
if (minindex != 10000)
{
for (int i = 0; i{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
printf("\nEng qisqa masofalar: \n");
for (int i = 0; iprintf("%5d ", d[i]);
int ver[SIZE];
int end = 4;
ver[0] = end + 1;
int k = 1;
int weight = d[end];
while (end != begin_index)
{
for (int i = 0; iif (a[i][end] != 0)
{
int temp = weight - a[i][end];
if (temp == d[i])
{
weight = temp;
end = i;
ver[k] = i + 1;
k++;
}
}
}
printf("\nEng qisqa n ni topish\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;}
Belman-Ford algoritmi yordamida eng qisqa yo'llarni topish
1) 1 dan 2 gacha bo'lgan masofa 2 ga teng
1) 1 dan 3 gacha bo'lgan masofa 3 ga teng
3) 1) 1 dan 4 gacha bo'lgan masofa 2 ga teng
4) 1) 1 dan 5 gacha bo'lgan masofa 5 ga teng
5) 1) 1 dan 6 gacha bo'lgan masofa 4 ga teng
6) 1) 1 dan 7 gacha bo'lgan masofa 8 ga teng
Cho'qqilarga eng qisqa masofalar:
• 1 dan 2 gacha teng (2)
• 1 dan 3 gacha teng (3)
• 1 dan 4 gacha teng (2)
• 1 dan 5 gacha teng (5)
• 1 dan 6 gacha teng (4)
• 1 dan 7 gacha teng (8)
Eng qisqa yo'l chiqishi:
1 dan 7 gacha teng (1 4 6 5)
Xulosa:
Mustaqil ish jarayonida biz Bellman-Ford algoritmidan foydalangan holda marshrutizatorlarni qurishni o'rgandik. Buning yordamida biz bir nuqtadan ikkinchisiga eng qisqa yo'llarni topamiz, bu yuqoridagi grafiklarda ko'rsatilgan.
NABIJONOV HAMIDJON 430_21
|
| |
