O'ZBЕKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI TOSHKЕNT AXBOROT
TЕXNOLOGIYALARI UNIVЕRSITЕTI
KOMPYUTER TARMOQLARI FANIDAN
MUSTAQIL ISH
MAVZU: Bellman-Ford algaritmlari asoslari paketlarini
mashurtlash
Bajardi: Turdaliyev Samandar
Tekshirdi: Qodirov Azamat
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;
}
|
