Telekommunikatsiya texnologiyalari “ fakulteti “Kompyuter injenering” kafedrasi

Bellman-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).

3. 
   Graflarning berilish usullari
   
1. 
   Quyidagi graf ko’rinishlari uchun matritsa quring va dastur kodini yozib natija oling.
   

1-masala: Grafning uchlarini bog’langanligini aniqlash dasturini tuzing. Va natijani matritsa ko’rinishda chop eting.


2-masala: Grafning n ta uchi bo’lib, u quyidagi kvadrat matritsani tashkil qiladi.



Grafning yoylari yo’naltirilgan yoki yo’naltirilmaganligini aniqlovchi dastur tuzing.


Dastur kodi:
#include
using namespace std;
int main(){
int n;
cout<<"Grafning tugunlari sonini kiriting: ";
cin>>n;
int k=0;
int a[n][n];
for(int i=0;i
for(int j=0;j
a[i][j]=rand()%2;
if(a[i][j]==1){
k++;
}
}
}
cout<<"Graf tugunlarining bog'liqlik matritsasi:\n"<<"(Random 0 va1 lar bilan to'ldirildi.)\n";
for(int i=0;i
for(int j=0;j
cout<
cout<<" ";
}
cout<<"\n";
}
int l=k/2;
cout<<"\nBu grafning qirralari soni "<
return 0;
}