|
Toshkent Axborot Texnalogiyalari Universiteti cal006- guruh talabasi Ilyosov Azizbekning Algaritmni loyihalash fanidan Mustaqil ish -1
|
| bet | 2/4 | | Sana | 18.05.2024 | | Hajmi | 341,76 Kb. | | #241448 |
Bog'liq Al1Bellman-Ford algoritmi - Algoritm tarixi uchta mustaqil matematiklar bilan bog'liq: Lester Ford, Richard Bellman va Edward Moore. Ford va Bellman algoritmni 1956 va 1958 yillarda nashr etishdi, Moore esa 1957 yilda taqdim qilgan. Va ba'zan uni Bellman-Ford-Moore algoritmi deb ham atashadi. Usul ba'zi vektorli-marshrutlash protokollarida, masalan, RIPda (Routing Information Protocol) qo'llaniladi. Deykstra algoritmi singari, Bellman-Ford algoritmi ham vaznga ega bo’lgan graflarda bitta tugundan qolgan barcha tugunlarga bo’lgan eng qisqa masofani aniqlashda ishlatiladi. Bu algoritm manfiy vaznga ega bo’lgan graflar bilan ishlashda ham qo’llanilishi mumkin (istisno holatlar ham mavjud).
G={V, E}, n=|V|, m=|E| graf berilgan bo’lsin. Qo’shni tugunlarni v va u deb, (v,u) orasidagi qirrani w deb belgilab olamiz. Boshqacha aytganda, v tugundan chiquvchi va u tugunga kiruvchi qirra vazni w ga teng. U holda, Bellman-Ford algoritmining muhim qismi quyidagicha ko’rinishga ega bo’ladi: I=1 dan n-1 gacha bajaramiz выполнять j=1 dan m gacha bajaramiz agar d[v] + w(v, u) < d[u] bo’lsa, u holda d[u] < d[v] + w(v, u) Har bir n-qadamda d[] massiv elementlari qiymatlarini yashilashga harakat qilinadi: agar w(v,u) qirra vazni va d[v] element qiymati yig’indisi d[u] qiymaridan kichik bo’lsa, u holda bu qiymat d[u] ga o’zlashtiriladi. - #include "stdafx.h"
- #include
- #define inf 100000
- using namespace std;
- struct Edges{
- int u, v, w;
- };
- const int Vmax=1000;
- const int Emax=Vmax*(Vmax-1)/2;
- int i, j, n, e, start;
- Edges edge[Emax];
- int d[Vmax];
//Bellman-Ford algoritmi void bellman_ford(int n, int s) { int i, j; for (i=0; i d[s]=0; for (i=0; i for (j=0; j if (d[edge[j].v]+edge[j].w d[edge[j].u]=d[edge[j].v]+edge[j].w;
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Toshkent Axborot Texnalogiyalari Universiteti cal006- guruh talabasi Ilyosov Azizbekning Algaritmni loyihalash fanidan Mustaqil ish -1
|
