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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_34.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_35.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_36.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_37.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_38.png)
![<< "\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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_39.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_41.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_42.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_43.png)
![/* 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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_44.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_45.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_46.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_47.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_48.png)
![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](/data/documents/63312e14-a6df-43ba-84c8-c27c0e98dc28/page_49.png)
TRANSPORT LOGISTIKASIDA GRAFLAR TATBIQ ETISH MUNDARIJA KIRISH……………………………………………………………… 3 1-BOB LOGISTIKA VA TRANPORT LOGISTIKASI, UNING ASOSIY TUSHUNCHASI ………………………............................. 6 1 .1 Logistika haqida asosiy tushunchalar………………………………... 6 1.2 Transport logistikasi…………………………………………………. 13 1.3 Ttansport logistikasida mash’rutlarni tashkil etish…………………... 20 1.4 Graflar nazariyasi elemenlari (graf, orgraf, zanjir, mashrut, grafni hosil qilish) …………………………………………………………… 25 2-BOB TRANSPORT LOGISTIKASIDA GRAFLARNI TATBIQ ETISH……………………………………………………………….. 30 2.1 Grafni hosil qilish.…………………………………………………… 30 2.2 Graf mashrutlarni hosil qilish. ............................................................. 36 2.3 Eng qisqa mashrutni aniqlash……………………………………….. 41 2.4 Graflar ustida amallar bajarish dasturiy ta’minoti…………………... 50 Xulosa……………………………………………………………….. 55 Foydalanilgan adabiyotlar.………………..……………………….. 56 Ilovalar 1
Kirish Masalaning qo‘yilishi. Transport logistikasida graflar tatbiq etish va daromad olish masalalarini tadqiq qilish va graflar ustida amallarni bajarish uchun qulay interfeysga ega bo‘lgan dasturiy ta‘minot yaratish. Mavzuning dolzarbligi. Jamiyatning barcha sohalarida transport logistikasini optimallashtirish muhum masala hisoblanadi. Ayniqsa bugungi kunda rivojlanayorgan, shiddat bilan sanoatlashayotgan jamiyatda, tabiiy holda raqobatning kuchayishi ortidan transport logistikasini optimal rejalashtirish va optimal daromad olish eng dolzarb masalalardan biri bo‘lib qolmoqda. Transport logistikasini optimallashtirish masalalari nazariy jihatdan, ya’ni ularning matematik modellarini yaratish ularni yechish va hakozolar, birmuncha yaxshiroq o‘rganilgan bo‘lishiga qaramay amaliy jihatda o‘rganishga yetarlicha ishlar mavjud bo‘lib bulardan biri bu nazariy tomondan yaratilgan modellar uchun dasturiy ta’minot yaratish. Shuning uchun bu ishda transport logistikasini samarali rejalashtirish va daromad olish masalalari uchun dasturiy taminot yaratish masalasi qaraladi. Ishning maqsad va vazifalari. Bitiruv malakaviy ishning asosiy maqsad va vazifasi bu tranport logistikasida graflar nazariyasini qullagan holda logistik joylashuv va boshqa parametrlariga ko‘ra transport logistikasidan eng samarali foydalanish yullarini aniqlash. Ilmiy-tatqiqot usullari. Ushbu bitiruv malakaviy ishida transport logistikasida graflarni tatbiq etish orqali ransport logistikasidan eng samarali foydalanish yullarini aniqlash dasturlash masalasiga keladigan hollar uchun o‘rganilgan bo‘lib bu modelni yechish uchun yaratilgan dasturiy ta’minot graflar nazariyasiga asoslangan. Mavzuning o‘rganilish darajasi. T ransport logistikasida graflarni tatbiq etish ni optimallashtirish masalasi nazariy jihatdan ko‘plab olimlar tomonida yaxshi o‘rganilgan bo‘lib ular ushbu masalaning turli xil modellarini yaratish va ularni yechish kabi natijalarni olishgan. Bu kabi natijalar keltirilgan ko‘plab adabiyotlar 2
mavzuni tadqiq qilishda o‘rganilgan. Mavzuning o‘rganilishi boshlang‘ch darajada bo‘lib, bu mavzuni o‘rganish natijasida olingan natija ya’ni yaratilga dasturiy ta’minot sodda bo‘lib u faqat bir yo‘nalishga mo‘ljallangan hisob kitoblarni bajaradi. Bu dasturiy ta’minotni kelajakda yanada mukammallashtirish rejalashtirilgan. Tadqiqotning ilmiy yangiligi. Bitiruv malakaviy ishida olingan natijalar amaliy-uslubiy xarakterga ega bo‘lib, ishda graflar nazariyasi ustida amallarni bajarishning ga mo‘ljallangan dasturiy ta’minot yaratligan. Bu dasturiy ta’minot JAVA dasturlash tilida yaratilgan bo‘lib, u vizuallashgan qulay interfeysga ega. Tadqiqot predmeti va ob’yekti. Tadqiqotning predmeti “Jarayonlar tadqiqoti”, “Transport logistikasi”, “Graflar nazariyasi”, “Matematik dasturlash” , “Java dasturlash tili” va shu kabi fan sohalari bo‘lib, ob’ekti ishlab chiqarishni rejalshtirish masalalarining matematik modellaridan iborat. Tatqiqotnig ilmiy va amaliy ahamiyati. Ishda olingan natijalar va unda qo‘llanilgan usullardan turli iqtisodiy, ijtimoiy sohalarning ko‘pgina amaliy masalalari, jumladan, transport logistikasida graflar nazariyasi tatbig‘i va samarali daromad olish masalalarini tadqiq qilishda, “Jarayonlar tadqiqoti”, “Transport logistikasi tadqiqoti”, “Transport logistikasida graflar nazariyasi tatbig‘ini matematik modellashtirish” va shu kabi fanlarning amaliy mashg‘ulotlari o‘quv jarayonlarida dasturiy vosita sifatida foydalanish mumkin. Ishning tuzilishi. Ushbu ish kirish, ikki bob, xulosa, foydalanilgan adabiyotlar ro‘yxati va ilovalardan iborat. I bob to‘rtta paragrafdan iborat bo‘lib, unda adabyotlardan foydalanilgan holda, bitiruv malakaviy ishiga qo‘yilgan “T ransport logistikasida graflar nazariyasi tatbig‘i” masalasi ni tavfislash va natija olish uchun zarur bo‘lgan asosiy tushunchalar, ta’riflar, tasdiqlar va matematik modellar keltirilgan. II bob to‘rtta paragrafdan iborat bo‘lib, transport logistikasida graflar nazariyasi tatbig‘ini tashkil etishda samarali reja va daromad olish masalalarining matematik modellari haqida so‘z yuritilgan, ikkinchi paragrafda bu modellardan foydalanilgan holda graflar ustida amallarni bajarishga asoslangan JAVA 3
dasturlash tilida qulay interfeysga ega bo‘lgan dasturiy ta’minotning funksional sxemasi keltirilgan hamda turli masalalarni yechish orqali dasturiy ta’minotdan foydalanuvchilar uchun ko‘rsatmalar berilgan . Uchinchi paragrafda dasturiy ta’minotning to‘gri ishlashini tekshirish uchun bir nechta mavjud standartlashgan dasturiy ta’minotlar bilan taqqoslashlar o‘tkazilgan. Olingan natijalarning qisqacha mazmuni. Bitiruv malakaviy ishida transport logistikasida graflar nazariyasi tatbig‘i masalalari va ularni yechish uchun olingan matematik modellar bilan tanishib chiqildi hamda bu modellardan foydalanilgan holda graflar ustida amallarni bajarishga asoslangan dasturiy ta’minot yaratildi. Bu dasturiy ta’minotdan foydalanib, graflar ustida ko‘plab amallarni bajarish mumkin bo‘lib, bu masalalarni transport logistikasida qo‘llash va samarali daromad olish masalalarining asosiy matematik modellaridan biri hisoblanadi. Ushbu yaratilgan dasturiy ta’minot graflar nazariyasiga asoslangan. Dasturiy ta’minot yordamida olingan yechimi transport logistikasidan foydalanishni optimal rejalashtirish va optimal daromad olishning yechimi bo‘ladi, ya’ni maqsad funksiyasining maksimumi optimal daromad olishga va shu funksiyani maksimumga erishtiruvchi o‘zgaruvchilarning qiymati optimal rejalarga mos keladi. 4
I BOB. LOGISTIKA VA TRANPORT LOGISTIKASI, UNING ASOSIY TUSHUNCHASI 1.1 Logistika haqida asosiy tushunchalar Logistika tushunchasi juda qadimiy tarixga ega bo‘lib, birinchi marta harbiy fan sifatida vujudga kelgan. IX asrda Vizantiyada bu tushunchaga qo‘shinni barcha kerakli narsalar bilan bilan o‘z vaqtida aniq ta’minlash jangning muvaffaqiyatini belgilovchi omil deb qaralgan. Vizantiya imperiyasida «logist» mansabi joriy etilgan boiib ular oziq-ovqat taqsimoti bilan shug‘ullanganlar. Ispan huquqshunosi va iqtisodchisi Polo de Ondegardoning 1572-yilda xabar berishicha ink Imperiyasi chinovniklari tomonidan ink saroyi uchun zarur bo‘lgan oziq-ovqat miqdorining hisobi olib borilgan. Bunda ularni qayerdan tashib keltirilishi, yetkazib kelish vaqti va tashish masofalarining hisoblari olib borilgan. XIX asrda fransuz olimi A.G. Jomini logistikani armiya va front orqasini boshqarish, tashishni rejalashtirish va tashkil etish bo‘yicha fan deb talqin etadi. 1850-yilda Sankt-Peterburgda chop etilgan «Harbiy ensiklopedik leksion»da logistika deb uzoqda va dushman yaqinida qo‘shinni ko‘chirishni boshqarish, qo‘shinni orqadan ta’minlashni tashkil etish san'ati deb tushuncha berilgan. Ikkinchi Jahon urushi davrida Amerika armiyasida logistik yondoshuv keng qo‘llanilgan. AQSh Ovrupoda jang qilganiga qaramay qo‘shinning ta’minoti juda yaxshi yo‘lga qo‘yilgan edi. Katta ingliz-rus lug‘atida hozir ham logistika tushunchasi harbiy ma’noda keltirilgan bo‘lib 1) front orqasi ta’minoti, 2) moddiytexnik ta’minot, 3) front orqasidagi ishlami bajarish va tashkil etish ma’nosida qo‘llaniladi. Respublikamizda va chet ellarda chop etilayotgan iqtisodiyotga oid adabiyotlarda logistika tushunchasi keng ma’noda qo‘llanilmoqda. Bugungi kunda iqtisodiy tizimdagi odamlar, moliyaviy, energetik va boshqa oqimlarni boshqarishlarga logistika fanining predmeti deb qaralyapti. Hozirda bank 5