Muhammad Al-Xorazmiy nomida Toshkent Axborot texnologiyalari universiteti
Mustaqil ish
Mavzu: Deysktra algoritimi asosida paketlarni marshrutlash
Bajardi: Abdumalikov Ilg’orbek
Tekshirdi: Amirsaidov Ulug’bek
Toshkent 2023
Grafikdagi grafik va manba cho'qqisini hisobga olgan holda, berilgan grafikdagi manbadan barcha cho'qqilarga eng qisqa yo'llarni toping. Dijkstra algoritmi Primning minimal oraliqli daraxt algoritmiga juda o'xshaydi. Prim MST-ga o'xshab, biz ildiz sifatida berilgan manba bilan SPT (eng qisqa yo'l daraxti) hosil qilamiz. Biz ikkita to'plamni saqlaymiz, bitta to'plam eng qisqa yo'l daraxtiga kiritilgan cho'qqilarni o'z ichiga oladi, boshqa to'plam hali eng qisqa yo'l daraxtiga kiritilmagan cho'qqilarni o'z ichiga oladi. Algoritmning har bir bosqichida biz boshqa to'plamdagi (hali kiritilmaganlar to'plami) va manbadan minimal masofaga ega bo'lgan cho'qqini topamiz. Quyida bitta manba cho'qqisidan berilgan grafikdagi barcha boshqa cho'qqilarga eng qisqa yo'lni topish uchun Dijkstra algoritmida qo'llaniladigan batafsil qadamlar keltirilgan.
Algoritm
1) Eng qisqa yo'l daraxtiga kiritilgan, ya'ni manbadan minimal masofa hisoblangan va yakunlangan cho'qqilarni kuzatib boruvchi sptSet to'plamini (eng qisqa yo'l daraxti to'plami) yarating. Dastlab, bu to'plam bo'sh.
2) Kirish grafigidagi barcha cho'qqilarga masofa qiymatini belgilang. Barcha masofa qiymatlarini INFINITE sifatida ishga tushiring. Manba cho'qqisiga masofa qiymatini 0 sifatida belgilang, shunda u birinchi bo'lib tanlanadi.
3) sptSet barcha cho'qqilarni o'z ichiga olmaydi
….a) sptSet da mavjud boʻlmagan va minimal masofa qiymatiga ega boʻlgan u uchini tanlang.
….b) u ni sptSetga kiriting.
….c) u ning barcha qo‘shni cho‘qqilarining masofa qiymatini yangilang. Masofa qiymatlarini yangilash uchun barcha qo'shni
cho'qqilarni takrorlang. Har bir qo'shni v cho'qqisi uchun, agar u (manbadan) masofa qiymati va u-v chetining og'irligi yig'indisi v ning masofa qiymatidan kichik bo'lsa, v ning masofa qiymatini yangilang.
#include
#include
#define V 9
int minDistance(int dist[], bool sptSet[]){
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n){
printf("Masofalar\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[V][V], int src){
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
int main(){
int graph[V][V] = { { 1, 0, 2, 4, 2, 0, 0, 0 },
{ 2, 2, 2, 0, 0, 0, 0, 0 },
{ 3, 4, 2, 0, 1, 0, 0, 0 },
{ 4, 2, 0, 1, 0, 0, 2, 6 },
{ 5, 0, 0, 0, 0, 0, 1, 3 },
{ 6, 0, 0, 3, 2, 1, 0, 4 },
{ 7, 0, 0, 0, 6, 3, 4, 0 }
};
dijkstra(graph, 0);
return 0;
}
|
