Muhammad Al-Xorazmiy nomida Toshkent Axborot texnologiyalari universiteti Mustaqil ish Mavzu: Bellman Ford algoritimi asosida paketlarni marshrutlash Bajardi: Abdumalikov Ilg’orbek Tekshirdi: Amirsaidov Ulug’bek Toshkent 2023

Muhammad Al-Xorazmiy nomida Toshkent Axborot texnologiyalari universiteti
Mustaqil ish


Mavzu: Bellman - Ford algoritimi asosida paketlarni marshrutlash


Bajardi: Abdumalikov Ilg’orbek
Tekshirdi: Amirsaidov Ulug’bek
Toshkent 2023

Grafikdagi src va manba uchi berilgan bo‘lsa, berilgan grafikdagi src dan barcha cho‘qqilarga eng qisqa yo‘llarni toping. Grafikda salbiy og'irlik qirralari bo'lishi mumkin. Biz ushbu muammo uchun Dijkstra algoritmini muhokama qildik. Dijkstra algoritmi ochko'z algoritm bo'lib, vaqt murakkabligi O((V+E)LogV) (Fibonachchi to'plamidan foydalangan holda). Dijkstra manfiy og'irlikdagi grafiklar uchun ishlamaydi, Bellman-Ford esa bunday grafiklar uchun ishlaydi. Bellman-Ford, shuningdek, Dijkstra-ga qaraganda sodda va taqsimlangan tizimlar uchun juda mos keladi. Ammo Bellman-Fordning vaqt murakkabligi O (V * E), bu Dijkstradan ko'proq.

Bellman-Ford algoritmidan foydalangan holda manbadan barcha cho'qqilarga eng qisqa masofani topish uchun qadamlar:

Bu qadam manbadan barcha cho'qqilargacha bo'lgan masofani cheksiz va manbaning o'zigacha bo'lgan masofani 0 sifatida ishga tushiradi.
|V| o'lchamdagi dist[] massiv yarating. dist[src] bundan mustasno, barcha qiymatlar cheksiz sifatida, bunda src manba cho'qqisidir. Ushbu qadam eng qisqa masofalarni hisoblab chiqadi. Quyidagini |V|-1 marta bajaring, bu erda |V| berilgan grafikdagi uchlari soni. Har bir chekka u-v uchun quyidagilarni bajaring Agar dist[v] > dist[u] + chekka uv og'irligi bo'lsa, dist[v] ni yangilang dist[v] = dist[u] + chekka uv og'irligi Ushbu bosqich grafikda salbiy og'irlik aylanishi mavjudligi haqida xabar beradi. Yana har bir chekkadan o'ting va har bir chekka u-v uchun amal qiling ……Agar dist[v] > dist[u] + chekka uv og‘irligi
bo‘lsa, “Grafikda manfiy og‘irlik sikli mavjud” 3-bosqichning g'oyasi shundan iboratki,
2-bosqich grafikda salbiy og'irlik tsikli bo'lmasa, eng qisqa masofalarni kafolatlaydi. Agar biz barcha qirralarni yana bir marta takrorlasak va har qanday cho'qqi uchun qisqaroq yo'lga ega bo'lsak, u holda manfiy og'irlik aylanishi mavjud.

U qanday ishlaydi?

Boshqa dinamik dasturlash muammolari singari, algoritm ham eng qisqa yo'llarni pastdan yuqoriga qarab hisoblab chiqadi. U birinchi navbatda yo'lda ko'pi bilan bitta chetiga ega bo'lgan eng qisqa masofalarni hisoblab chiqadi. Keyin, u eng ko'p 2 qirrali eng qisqa yo'llarni hisoblab chiqadi va hokazo. Tashqi halqaning i-iteratsiyasidan so'ng, eng ko'p i qirralari bo'lgan eng qisqa yo'llar hisoblanadi. Maksimal |V| bo'lishi mumkin – har qanday oddiy yo‘lda 1 ta chekka, shuning uchun tashqi halqa |v| ishlaydi - 1 marta. Fikr shundan iboratki, agar biz eng ko'p i qirralari bo'lgan eng qisqa yo'llarni hisoblagan bo'lsak, manfiy og'irlik tsikli yo'q deb faraz qilsak, u holda barcha qirralarning iteratsiyasi eng ko'p (i+1) qirralar bilan eng qisqa yo'lni berishni kafolatlaydi.
Quyida yuqoridagi algoritmning tasviri keltirilgan:

1-qadam : Berilgan manba uchi 0 bo'lsin. Manbaning o'ziga bo'lgan masofadan tashqari barcha masofalarni cheksiz deb boshlang. Grafikdagi cho'qqilarning umumiy soni 5 ga teng, shuning uchun barcha qirralar 4 marta qayta ishlanishi kerak.

2-qadam : Barcha qirralarning quyidagi tartibda ishlov berilsin: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), ( B, C), (E, D). Barcha qirralarning birinchi marta ishlov berilganda biz quyidagi masofalarni olamiz. Birinchi qatorda dastlabki masofalar ko'rsatilgan. Ikkinchi qatorda qirralar (B, E), (D, B), (B, D) va (A, B) ishlov berilganda masofalar ko'rsatilgan. Uchinchi qatorda (A, C) ishlov berilganda masofalar ko'rsatilgan. To'rtinchi qatorda (D, C), (B, C) va (E, D) qachon qayta ishlanishi ko'rsatilgan.

3-qadam : Birinchi iteratsiya ko'pi bilan 1 chekka uzunlikdagi barcha eng qisqa yo'llarni berishni kafolatlaydi. Barcha qirralarning ikkinchi marta ishlov berilganda biz quyidagi masofalarni olamiz (oxirgi qator yakuniy qiymatlarni ko'rsatadi).

4-qadam : Ikkinchi iteratsiya ko'pi bilan 2 chekka uzunlikdagi barcha eng qisqa yo'llarni berishni kafolatlaydi. Algoritm barcha qirralarni yana 2 marta qayta ishlaydi. Ikkinchi takrorlashdan keyin masofalar minimallashtiriladi, shuning uchun uchinchi va to'rtinchi iteratsiyalar masofalarni yangilamaydi.

#include

using namespace std;
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}

void printArr(int dist[], int n){

printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}

void BellmanFord(struct Graph* graph, int src){

int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX
&& dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return;
}
}
printArr(dist, V);

return;
}

int main(){

int V = 5; // Number of vertices in graph
int E = 8; // Number of edges in graph
struct Graph* graph = createGraph(V, E);

// add edge 0-1 (or A-B in above figure)

graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;

// add edge 0-2 (or A-C in above figure)

graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;

// add edge 1-2 (or B-C in above figure)

graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;

// add edge 1-3 (or B-D in above figure)

graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;

// add edge 1-4 (or B-E in above figure)

graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;

// add edge 3-2 (or D-C in above figure)

graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;

// add edge 3-1 (or D-B in above figure)

graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;

// add edge 4-3 (or E-D in above figure)

graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
// Function call
BellmanFord(graph, 0);

return 0;

}