Transport logistikasida graflar tatbiq etish
![int val, cost;
adjNode* next;
};
// qirralarni saqlash uchun tuzilish
struct graphEdge {
int start_ver, end_ver, weight;
};
class DiaGraph{
// berilgan grafdan qo‘shnilar ro‘yxatiga yangi tugunlarni qo‘shing
adjNode* getAdjListNode(int value, int weight, adjNode* head) {
adjNode* newNode = new adjNode;
newNode->val = value;
newNode->cost = weight;
newNode->next = head; // yangi tugunni joriy boshga yo‘naltiring
return newNode;
}
int N; // grafdagi tugunlar soni
public:
adjNode **head; //ko‘rsatkichlar massivi sifatida qo‘shnilik ro‘yxati
// Konstruktor
DiaGraph(graphEdge edges[], int n, int N) {
// yangi tugunni ajratish
head = new adjNode*[N]();
this->N = N;
// barcha uchlari uchun bosh ko‘rsatgichni ishga tushiring
for (int i = 0; i < N; ++i)
head[i] = nullptr;
// unga qirralar qo‘shish orqali yo‘naltirilgan grafni tuzing
for (unsigned i = 0; i < n; i++) {
int start_ver = edges[i].start_ver;
int end_ver = edges[i].end_ver;
int weight = edges[i].weight;
// boshida kiriting
adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
// bosh ko‘rsatgichni yangi tugunga yo‘naltiring
head[start_ver] = newNode;
}
}
// Destruktor
~DiaGraph() {
for (int i = 0; i < N; i++)
delete[] head[i];
delete[] head;
}
};
// berilgan uchning barcha qo‘shni uchlarini chop eting
34](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_34.png?v=1)
![void display_AdjList(adjNode* ptr, int i)
{
while (ptr != nullptr) {
cout << "(" << i << ", " << ptr->val
<< ", " << ptr->cost << ") ";
ptr = ptr->next;
}
cout << endl;
}
// grafni amalga oshirish
int main()
{
// Graf qirralari massivi.
graphEdge edges[] = {
// (x, y, w) -> og‘irligi w bilan x dan y gacha bo‘lgan chekka
{0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
};
int N = 6; // Grafdagi uchlar soni
// qirralarning sonini hisoblash
int n = sizeof(edges)/sizeof(edges[0]);
// graf qurish
DiaGraph diagraph(edges, n, N);
// grafning qo‘shnilik ro‘yxati tasvirini chop etish
cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
for (int i = 0; i < N; i++)
{
// i uchsining qo‘shni uchlarini ko‘rsatish
display_AdjList(diagraph.head[i], i);
}
return 0;
}
2.2 Graf mashrutlarni hosil qilish
Graf va uning tasvirlari
Graf ma'lumotlar strukturasi bo‘lib, quyidagi ikkita komponentdan iborat:
1. Uchlarning chekli to‘plami tugunlar deb ham ataladi.
2. (u, v) ko‘rinishdagi tartiblangan juftlikning chekli to‘plami chekka deb
ataladi. Juftlik tartiblangan, chunki (u, v) yo‘naltirilgan graf (di-graf) holatida (v,
u) bilan bir xil emas. Shakl juftligi (u, v) uch u dan v uchgacha chekka borligini
bildiradi. Qirralarda og‘irlik/qiymat/narx bo‘lishi mumkin.
35](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_35.png?v=1)
![Graflar ko‘plab real hayot ilovalarini ko‘rsatish uchun ishlatiladi: Graflar
tarmoqlarni ifodalash uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog‘i
yoki elektron tarmoqdagi yo‘llarni o‘z ichiga olishi mumkin. Graflar linkedIn,
Facebook kabi ijtimoiy tarmoqlarda ham qo‘llaniladi. Masalan, Facebook-da har
bir shaxs tepa (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilma bo‘lib, shaxs
identifikatori, ismi, jinsi va mahalliy til kabi ma'lumotlarni o‘z ichiga oladi.
Grafning qo‘shimcha ilovalari uchun buni ko‘ring.
Quyida 5 ta burchakli yo‘naltirilmagan graf misoli keltirilgan.
Quyidagi ikkitasi grafning eng ko‘p ishlatiladigan tasvirlari.
1. Qo‘shnilik matritsasi
2. Qo‘shnilar ro‘yxati
Insidans matritsasi va Insidans List kabi boshqa ko‘rinishlar ham mavjud.
Graf tasvirni tanlash vaziyatga xosdir. Bu butunlay bajariladigan operatsiyalar
turiga va foydalanish qulayligiga bog‘liq.
Qo‘shnilik matritsasi:
Qo‘shnilik matritsasi - bu V x V o‘lchamdagi 2D massiv, bu erda V -
grafdagi uchlar soni. 2D massiv adj[][] bo‘lsin, slot adj[i][j] = 1 i -uchdan j -
uchgacha qirra (yoy) borligini bildiradi. Yo‘naltirilmagan graf uchun qo‘shnilik
matritsasi har doim simmetrikdir. Qo‘shnilik matritsasi vaznli graflarni ko‘rsatish
uchun ham ishlatiladi. Agar adj[i][j] = w bo‘lsa, u holda i uchdan j uchgacha w
og‘irligi bilan chekka mavjud.
Yuqoridagi misol graf uchun qo‘shnilik matritsasi:
36](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_36.png?v=1)
![Taqqoslash mumkinki, vakillikni amalga oshirish va kuzatish osonroq.
Chetni olib tashlash O (1) vaqtni oladi. “u” uchsidan “v” uchsiga chekka bor-
yo‘qligi kabi so‘rovlar samarali va O(1) ni bajarish mumkin.
Kamchiliklari: O(V^2) ko‘proq joy sarflaydi. Graf siyrak bo‘lsa ham
(kamroq chekkalarni o‘z ichiga oladi), u bir xil joyni egallaydi. Uch qo‘shilishi
O(V ^ 2) vaqtidir. Bir uchning barcha qo‘shnilarini hisoblash O (V) vaqtni oladi
(samarali emas).
Iltimos, qo‘shnilik matritsasining Python ilovasi namunasi uchun buni
ko‘ring.
Qo‘shni matritsa uchun kirishni amalga oshirish C++ da
#include <iostream>
using namespace std;
int main()
{
// n uchlari soni
// m - qirralarning soni
int n, m;
cin >> n >> m ;
int adjMat[n + 1][n + 1];
for(int i = 0; i < m; i++){
int u , v ;
cin >> u >> v ;
adjMat[u][v] = 1 ;
adjMat[v][u] = 1 ;
}
return 0;
}
37](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_37.png?v=1)
![Qo‘shnilar ro‘yxati:
Ro‘yxatlar massivi ishlatiladi. Massivning o‘lchami uchlari soniga teng.
Massiv [] massiv bo‘lsin. Kirish massivi[i] i-chi uchga qo‘shni uchlar ro‘yxatini
ifodalaydi. Ushbu tasvirdan vaznli grafni ifodalash uchun ham foydalanish
mumkin. Qirralarning og‘irligi juftliklar ro‘yxati sifatida ifodalanishi mumkin.
Quyida yuqoridagi grafning qo‘shnilik ro‘yxati ko‘rsatilgan.
E'tibor bering, quyida keltirilgan dasturda biz bog‘langan ro‘yxat o‘rniga
qo‘shni ro‘yxatlarni ko‘rsatish uchun dinamik massivlardan (Java'da
C++/ArrayList'dagi vektor) foydalanamiz. Vektorni amalga oshirish kesh
qulayligining afzalliklariga ega.
// STL yordamida grafning oddiy tasviri
#include <bits/stdc++.h>
using namespace std;
// Kengay qo‘shish uchun yordamchi dastur
// yo‘naltirilmagan graf.
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Qo‘shnilar ro‘yxatini chop etish uchun yordamchi dastur
// graf tasviri
void printGraph(vector<int> adj[], int V)
{
for (int v = 0; v < V; ++v) {
cout << "\n Adjacency list of vertex " << v
38](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_38.png?v=1)
![<< "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
// asosiy kodi
int main()
{
int V = 5;
vector<int> adj[V];
addEdge(adj, 0, 1);
addEdge(adj, 0, 4);
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 3);
addEdge(adj, 3, 4);
printGraph(adj, V);
return 0;
}
Natija
0 uchsining qo‘shnilik ro‘yxati
head -> 1-> 4
1-uchning qo‘shnilik ro‘yxati
head -> 0-> 2-> 3-> 4
2-uchning qo‘shnilik ro‘yxati
head -> 1-> 3
3 uchsining qo‘shnilik ro‘yxati
head -> 1-> 2-> 4
4-uchning qo‘shnilik ro‘yxati
head -> 0-> 1-> 3
Taroziga soling: joyni tejaydi O(|V|+E|) . Eng yomon holatda, grafda C(V,
2) chekka soni bo‘lishi mumkin, shuning uchun O(V^2) bo‘sh joy sarflanadi. Uch
qo‘shish osonroq. Bir uchning barcha qo‘shnilarini hisoblash optimal vaqtni oladi.
Kamchiliklari: U uchdan v uchgacha chekka bor-yo‘qligi kabi so‘rovlar
samarali emas va O(V) ni bajarish mumkin.
Hayotiy masalalarda graflar siyrak (E| <<|V|2). Shuning uchun qo‘shni
ro‘yxatlar Ma'lumotlar strukturasi odatda graflarni saqlash uchun ishlatiladi.
Qo‘shnilik matritsasi bunday algoritmlar uchun vaqtga bog‘liq murakkablikni (|V|
2) amalga oshiradi.
39](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_39.png?v=1)
![Deykstra algoritmi
Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang‘ich
berilgan tugunidan boshlab qolgan barcha tugunlargacha bo‘lgan barcha eng qisqa
yo‘llarni topadi. Uning yordamida, agar barcha zarur ma'lumotlar berilgan bo‘lsa,
masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan
boshqa shaharlarning har biriga borish uchun qaysi yo‘llar ketma-ketligini tanlash
afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki,
manfiy vaznga ega bo‘lgan qirralari mavjud bo‘lgan graflarni qayta ishlash
imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun
foydasiz bo‘lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun
Dijkstraning algoritmidan foydalanib bo‘lmaydi.
Algoritmni dasturiy ta'minotini amalga oshirish uchun ikkita massiv kerak
bo‘ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi
ma'lumotlarni saqlash uchun va topilgan eng qisqa yo‘llar kiritiladigan butun
toifadagi - distance . G={V,E} graf berilgan bo‘lsin. V to‘plamga tegishli barcha
tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited massivining
elementlariga false qiymat berib chiqiladi. Eng afzal yo‘lni topish masalasi
qaralyapti. Distance massivining har bir elementiga shunday qiymat beriladiki,
ixtiyoriy potensial yo‘ldan katta bo‘lsin (odatda, bu qiymatni cheksiz katta qiymat
deb qaraladi, ammo dasturda berilgan toifaning qiymatlar diapazonidagi eng katta
qiymat sifatida olinadi). Boshlang‘ich nuqta sifatida s tugun tanlanadi va unga nol
yo‘l belgilanadi: distance [s] = 0, chunki s-dan s-gacha hech qanday qirra yo‘q (bu
usulda ilmoqlar qaralmaydi).
Shundan keyin, barcha qo‘shni tugunlar topiladi (s dan chiquvchi qirralar
orqali) [ularni t va u deb belgilaylik] va ular birma-bir tekshirib ko‘riladi, ya'ni s
tugundan har bir tugungacha birma-bir marshrut bahosi hisoblanadi:
- distance[t]=distance[s]+ s va t orasidagi qirraning vazni;
- Distance[u]=distance[s]+ s va u orasidagi qirraning vazni.
41](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_41.png?v=1)
![Ehtimoldan xoli emaski, u yoki bu tugunga s dan bir qancha yo‘llar bo‘lishi
mumkin. Shu sababli, distance massivida bu tugunga bo‘lgan yo‘lning vaznini
qayta ko‘rib chiqish kerak bo‘ladi. Shunda kattaroq (nooptimal) qiymat yo‘qotiladi
va tugunga mos yo‘lning vazniga kichikroq qiymat beriladi. s tugun bilan
qo‘shni bo‘lgan va qarab chiqilgan tugunlar tashrif buyurilgan sifatida belgilab
chiqiladi, yani visited[s]=true va natijada, s dan chiquvchi, minimal vaznga ega
bo‘lgan yo‘l eltuvchi tugun faol element sifatida belgilab olinadi. Faraz qilamiz, s
dan u gacha masofa t ga qaraganda qisqa bo‘lsin. Kelib chiqadiki, u tugun
faollashadi va yuqoridagi kabi uning qo‘shnilari ( s dan tashqari) o‘rganilib
chiqiladi. u tugun tashrif buyurilgan deb belgilanadi: visited[u]=true, endi t tugun
faollashadi va yuqoridagi prosedura uning uchun takrorlanadi. Deykstra algoritmi s
tugundan borish mumkin bo‘lgan barcha tugunlar tadqiq qilinmaguncha davom
ettiriladi.
C++ da dastur kodi
#include <iostream>
using namespace std;
#include <limits.h>
// Grafdagi uchlar soni
#define V 9
// Minimal masofa qiymatiga ega uchni topish uchun yordamchi funktsiya, dan
// eng qisqa yo‘l daraxtiga hali kiritilmagan uchlar to‘plamiint minDistance(int dist[], bool
sptSet[])
{
// Minimal qiymatni ishga tushiring
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;
}
// Tuzilgan masofa massivini chop etish uchun yordamchi funksiya
void printSolution(int dist[])
{
cout <<"Vertex \t Distance from Source" << endl;
42](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_42.png?v=1)
![for (int i = 0; i < V; i++)
cout << i << " \t\t"<<dist[i]<< endl;
}
// Dijkstraning yagona manbali eng qisqa yo‘l algoritmini amalga oshiradigan funksiya
// qo‘shni matritsa ko‘rinishidan foydalangan holda tasvirlangan graf uchun
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// src dan i gacha bo‘lgan masofa
bool sptSet[V]; // sptSet[i] i uch eng qisqasiga kiritilgan bo‘lsa rost bo‘ladi
// yo‘l daraxti yoki src dan i gacha bo‘lgan eng qisqa masofa yakunlandi
// Barcha masofalarni INFINITE va stpSet[] ni noto‘g‘ri deb boshlang
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Manba uchsining o‘zidan masofa har doim 0 ga teng
dist[src] = 0;
// Barcha uchlar uchun eng qisqa yo‘lni toping
for (int count = 0; count < V - 1; count++) {
// Yo‘q uchlar to‘plamidan minimal masofa uchsini tanlang
// hali qayta ishlangan. u birinchi iteratsiyada har doim src ga teng.
int u = minDistance(dist, sptSet);
// Tanlangan uchni qayta ishlangan deb belgilang
sptSet[u] = true;
// Tanlangan uchning qo‘shni uchlarining dist qiymatini yangilang.
for (int v = 0; v < V; v++)
// dist[v] ni yangilash faqat sptSet da bo‘lmasa, dan chekka mavjud
// u dan v gacha va src dan v gacha bo‘lgan yo‘lning umumiy og‘irligi
// dist[v] ning joriy qiymatidan kichikroq
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// tuzilgan masofa massivini chop eting
printSolution(dist);
}
// Yuqoridagi funktsiyani sinab ko‘rish uchun bajaruvchi dasturi
int main()
{
43](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_43.png?v=1)
![/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
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).
s tugundan qolgan barcha tugunlargacha bo‘lgan qisqa masofani Bellman-
Ford algoritmidan foydalanib topish dinamik dasturlashtirish usulini qo‘llash
demakdir, ya’ni uni qism masalalarga ajratib, ularni yechimi orqali umumiy asosiy
masalani hal qilishdir. Bunda qism masala bo‘lib, bitta alohida qaralayotgan
tugundan boshqasigacha eng qisqa yo‘lni aniqlash masalasi hisoblanadi. Algoritm
natijalarini saqlash uchun d[] bir o‘lchovli massiv qabul qilamiz. Uning har bir i-
elementida s gundan i-elementgacha qisqa masofa qiymatini saqlanadi (agar
mavjud bo‘lsa). Dastlab, d[] massiv elementlariga shartli sheksiz katta qiymat
berib chiqiladi, d[s] ga 0 o‘zlashtiriladi.
44](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_44.png?v=1)
![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 <iostream>
#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<n; i++) d[i]=inf;
d[s]=0;
for (i=0; i<n-1; i++)
for (j=0; j<e; j++)
if (d[edge[j].v]+edge[j].w<d[edge[j].u])
d[edge[j].u]=d[edge[j].v]+edge[j].w;
for (i=0; i<n; i++) if (d[i]==inf)
cout<<endl<<start<<"->"<<i+1<<"="<<"Not";
else cout<<endl<<start<<"->"<<i+1<<"="<<d[i];
}
//asosiy funksiya
void main()
{
45](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_45.png?v=1)
![int w;
cout<<"tugunlar soni > "; cin>>n;
e=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<" Вес "<<i+1<<"->"<<j+1<<" > "; cin>>w;
if (w!=0)
{
{
edge[e].v=i;
edge[e].u=j;
edge[e].w=w;
e++; } }
cout<<"boshlang‘ich tugun > "; cin>>start;
cout<<"qisqa masofalar ro‘yhati:";
bellman_ford(n, start-1);
system("pause>>void"); }
Bu yerda graf soddalashtirilgan qirralar ro‘yhati ko‘rinishida ifodalangan va
foydalanuvchi tomonidan vazn matrisasi kiritiladi. Bellman-Ford algoritmining
asosiy qismi m*(n-1) marta bajariladi, tashqi sik n-1 marta takrorlanadi, ichki sikl
esa m marta. N-iterasiyadan voz kechish esa maqsadga muvofiqdir, chunki
algoritm n-1 ta iterasiyada ham o‘z vazifasini to‘liq amalga oshira oladi. Ammo
tashqi siklni n marta amalga oshirish grafda manfiy sikl mavjudligini aniqlashga
imkon beradi.
Floyd-Uorshell algoritmi
Bu usulning nomlanishi 1962 yilda bir vaqtning o‘zida kashf etgan ikkita
amerikalik tadqiqotchilar Robert Floyd va Stiven Uorshell sharafiga qo‘yilgan.
Nomlanishning boshqa variantlari kamroq tarqalgan: Roy - Uorshall algoritmi yoki
Roy - Floyd algoritmi. Roy - bu algoritmni hamkasblaridan 3 yil oldin (1959 yilda)
ishlab chiqqan professorning familiyasidir, ammo uning kashfiyoti nashr qilimay
qolgan. Floyd-Uorshell algoritmi – grafning har bir tugunigacha bo‘lgan qisqa
masofalarni hisoblashning dinamik algoritmidir. Bu metodni musbat va manfiy
vaznga ega bo‘lgan graflarda qo‘llash mumkin, faqat manfiy sikllardan tashqari.
Shu sababli oldin ko‘rib o‘tilgan Deykstra algoritmiga qaraganda umumiyroq
46](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_46.png?v=1)
![hisoblanadi. Floyd-Uorshell algoritmini amalga oshirish uchun har bir tuguni 1 dan
|V| gacha nomerlangan G=(V,E) grafning qo‘shma matrisasi D[][] ni tashkil
etamiz. Bu matrisa |V|x|V| o‘lchamga ega bo‘ladi va har bir D[i][j] elementga i dan
j gacha bo‘lgan qirralarning vazni o‘zlashtiriladi. Algoritm bajarilishi mobaynida
ushbu matrisa qayta yoziladi: uning har bir yacheykasiga i tugundan j tugungacha
hisoblangan eng optimal, qisqa masofa yoziladi. Endi algoritmning asosiy qismini
tuzishdan oldin, eng qisqa yo‘llarning matritsasi tarkibini tushunish kerak. Uning
har bir elementi D[i][j] mavjud bo‘lgan marshrutlarning eng kichikini o‘z ichiga
olishi kerakligi sababli, biz darhol ayta olamizki, yagona tugundan uchun u nolga
teng, hattoki pastadir (manfiy sikllar hisobga olinmaydi), shuning uchun asosiy
diagonalning barcha elementlari (D[i][i]) ni 0 qilish kerak.
Diagonalda bo‘lmagan 0 qiymatli elementlar (matrisaning i va j tugunlari
o‘rtasida bevosita qirra mavjud bo‘lmagan joylarida nollar bo‘lishi mumkin)
ularning qiymatini iloji boricha o‘zgartirish uchun biz ularni cheksizlik bilan
tenglashtiramiz, bu dasturda bo‘lishi mumkin, masalan, grafda mumkin bo‘lgan
maksimal yo‘l, yoki shunchaki katta son. Algoritmning uchta - sikl, ifoda va shartli
operatordan iborat asosiy qismi juda ixcham tarzda yoziladi:
- k=1 dan |V| gacha bajariladi
- i=1 dan |V| gacha bajariladi
- j=1 dan |V| gacha bajariladi
- agar D[i][k]+D[k][j]<D[i][j] bo‘lsa, u holda D[i][j] ←D[i][k]+D[k][j]
i tugunidan j tugunigacha eng qisqa yo‘l ular orqali va boshqa tugunlar
to‘plamidan o‘tishi mumkin k ∈ (1, ..., |V|). i dan j gacha bo‘lgan yo‘l k tugundan
o‘tishi yoki o‘tmasligi ham mumkin. Agar boshqa yo‘l mavjud bo‘lsa, u i dan k ga,
keyin k dan j gacha o‘tishini anglatadi, shuning uchun u qisqa yo‘lning qiymati
D[i][j] ni D[i][k] + D[k][j] yig‘indi bilan almashtirish kerak.
Floyd-Worshell algoritmining to‘liq kodini C ++ va Paskalda ko‘rib chiqamiz
va keyin u bajaradigan harakatlar ketma-ketligini batafsil tahlil qilamiz.
47](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_47.png?v=1)
![C++ da dastur kodi:
#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
// Floyd-Uorshall algoritmi
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;
for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
} }
// asosiy funksiyasi
void main()
{
setlocale(LC_ALL, "Rus");
cout<<" Grafdagi uchlar soni > "; cin>>n;
cout<<" Kenar og‘irlik matritsasini kiriting:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<" Eng qisqa yo‘l matritsasi:"<<endl;
FU(GR, n);
system("pause>>void");
}
Tasavvur qilaylik, har bir elementi vazn haqida ma’lumot saqlovchi qo‘shma
matritsa quyidagicha berilgan bo‘lsin:
48](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_48.png?v=1)
![Quyidagi grafda tugunlar soni 3 ga teng va u quyidagi matrisa bilan berilgan.
Algoritm masalasi:
Matrisani shunday qayta yozish kerakki, undagi har bir element i va j tugun
orasidagi qirra vaznini emas, balki I dan j gacha qisqa yo‘l vaznini saqlasin. Misol
uchun kichik bir graf olamiz. Shu sababli undagi qiymatlar deyarli o‘zgarmasligi
ham mumkin. Ammo dastur narijasida unda 2ta element qiymati almashganligini
ko‘rish mumkin.
Ushbu jadvalda algoritmning asosiy qismini ifodalovchi 27ta bosqichi
keltirilgan. Usulning bajarilish vaqti O(|V| 3
) bo‘lganligi sababli bosqichlar soni
shunchalik ko‘p. Graf 3 ta tugunga ega va 3 3
=27 ga teng. Birinchi o‘zgarish k = 1, i
= 2 va j = 3 bo‘lgandagi iteratsiyada sodir bo‘ladi. Bunda D[2][1]=1, D[1][3]=2,
D[2][3]=4. Shart to‘g‘ri, ya'ni D[1][3] + D[3][2] = 3 va 3 <4, shuning uchun D[2]
[3] matritsa elementi yangi qiymat oladi. Keyingi qadam, shart bajarilganda
ikkinchi satr va uchinchi ustunda joylashgan elementga haqiqatan ham o‘zgarishlar
kiritiladi.
2.4 Graflar ustida amallar bajarish dasturiy ta’minoti
Ushbu dasturiy ta’minotni yaratishda men Java dasturlash tilidan
foydalandim. Ushbu dasturiy ta’minot kompyuterlarda foydalanish uchun
muljallangan bo‘lib vizuallashgan qulay interfeysga ega. Ushbu dasturiy
49](https://docx.uz/documents/87d2c2f2-5b5e-48e3-9b6e-20adc49a0f7f/page_49.png?v=1)
Transport logistikasida graflar tatbiq etish