27
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
TRANSPORT YO‘LLARIDA MINIMAL MASOFALARNI
HISOBLASHDA DEYKSTRI ALGORITIMINING AHAMIYATI
Farmonov Sherzodbek Raxmonjonovich
Fargʻona davlat universiteti amaliy matematika va informatika kafedrasi
katta o’qituvchisi
farmonovsh@gmail.com
Akbarov Ravshanbek Azizjon oʻgʻli
Fargʻona davlat universiteti talabasi
ravshanbekakbarov606@gmail.com
https://doi.org/10.5281/zenodo.14203503
ARTICLE INFO
ABSTRACT
Qabul qilindi: 9-noyabr 2024 yil
Ma’qullandi: 19-noyabr 2024 yil
Nashr qilindi: 21-noyabr 2024 yil
Ushbu maqolada Deykstra algoritmining eng
qisqa yo‘lni topishdagi samaradorligi, amaliy
qo‘llanilishi va cheklovlari tahlil qilinadi. Shuningdek,
algoritmning A* kabi boshqa algoritmlar bilan
solishtirilishi va samaradorlikni oshirish uchun
takomillashtirish imkoniyatlari ko‘rib chiqiladi.
KEY WORDS
Deykstra algoritmi, eng
qisqa yo‘l, yo‘l topish algoritmlari,
graf
nazariyasi,
transport
tarmoqlari, telekommunikatsiya,
A* algoritmi, dinamik dasturlash,
samaradorlik,
hisoblash
murakkabligi, yo‘nalishli graf,
algoritm optimallashtirish, ikki
tomonlama
qidiruv,
parallel
dasturlash, matematik asos
Muammo yoki mavzu haqida qisqacha tanishtirish
: Deykstra algoritmi grafdagi eng qisqa
yo'lni topish uchun ishlab chiqilgan samarali algoritmlardan biri hisoblanadi. Bu algoritm,
odatda, grafikdagi bir nuqtadan boshqa barcha nuqtalarga bo'lgan eng qisqa masofani
hisoblash uchun ishlatiladi. Grafik nazariyasida yo'l topish algoritmlarining asosiy vazifasi bir
nuqtadan boshqasiga o'tish yo'lini eng qisqa masofa yoki eng kam xarajat bilan aniqlashdir.
Deykstra algoritmi, ayniqsa, ijobiy og'irlikli grafiklar uchun juda qulay va samarali bo'lib,
yo'nalishli va yo'nalishsiz grafiklarda foydalanilishi mumkin. Ushbu algoritmning ishlash
prinsipi shundaki, u grafikda eng qisqa yo'lni topish uchun bosqichma-bosqich eng kam
og'irlikli yo'lni tanlaydi va barcha mumkin bo'lgan yo'llarni ko'rib chiqadi. Shunday qilib,
algoritmning xotira va vaqt jihatdan samaradorligi, ayniqsa, katta grafiklarda eng qisqa yo'l
topish uchun muhim hisoblanadi.
Deykstra algoritmining qo'llanilish sohalari keng. Uni eng ko'p qo'llanadigan sohalardan biri
transport va navigatsiya tizimlari bo'lib, bu algoritm har xil shaharlar yoki hududlar orasidagi
eng qisqa yo'lni topish uchun foydalaniladi. Shuningdek, aloqa tarmoqlari va kompyuter
tarmoqlarida ma'lumotlarni samarali uzatish yo'llarini topishda, logistika va yetkazib berish
tizimlarida, va hattoki, video o'yinlarda ham foydalaniladi. Ushbu algoritm ma'lumotlarni
optimallashtirish va resurslarni tejash imkoniyatlarini beradi, bu esa ko'p tarmoqlarda
iqtisodiy va samaradorlik jihatdan muhim ahamiyatga ega.
Ushbu maqola Deykstra algoritmining ishlash tamoyillari va uning amaliy qo'llanilishini
tushuntirish maqsadida yozilgan. Maqsad — Deykstra algoritmini graf nazariyasida va
kundalik hayotda qanday foydalanilishini tahlil qilish va uni ishlatishdagi asosiy qadamlarni
o'rganish. Maqolada algoritmning matematik asoslari, ishlash prinsipi, va uni amalga oshirish
28
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
uchun zarur bo'lgan qadamlar batafsil ko'rib chiqiladi. Shuningdek, algoritmni real
loyihalarda qanday qilib qo'llash mumkinligi haqida amaliy misollar keltiriladi. Ushbu maqola
nafaqat algoritmni tushuntirish, balki uning muammolarni yechishdagi afzalliklari va
cheklovlari haqida ham tushunchalar beradi.
Graf nazariyasi va yo'l topish algoritmlari transport tizimlari, kompyuter tarmoqlari,
telekommunikatsiya, logistika va boshqa ko'plab sohalarda muhim ahamiyatga ega. Har bir
tizimda ob'ektlar orasidagi masofani minimallashtirish yoki optimal yo'lni topish muhim
hisoblanadi. Masalan, transport tizimlarida yo'lovchilar yoki yuklarni bir nuqtadan
boshqasiga yetkazishda minimal vaqt va xarajatni topish zarur bo'ladi. Kompyuter
tarmoqlarida esa, ma'lumotlarni bir serverdan ikkinchisiga eng qisqa yo'l orqali uzatish
tarmoq samaradorligini oshiradi.
Shunday qilib, grafdagi eng qisqa yo'lni aniqlashning muhimligi kundalik hayotdagi ko'plab
tizimlarning samarali ishlashida namoyon bo'ladi. Shu munosabat bilan, Deykstra algoritmi
eng qisqa yo'lni topish uchun samarali va keng qo'llaniladigan usullardan biri bo'lib, transport
va telekommunikatsiya sohalarida katta ahamiyat kasb etadi.
Algoritmning natijalari va samaradorligi
: Deykstra algoritmi turli grafiklarda eng qisqa
yo'lni aniqlashda yuqori samaradorlik ko‘rsatadi, ayniqsa ijobiy og‘irlikli grafiklarda eng aniq
natijalarni beradi. Bu algoritmda barcha tugunlar tekshirilgani sababli, algoritm butun graf
bo‘ylab eng qisqa masofalarni aniq aniqlab beradi. Masalan, quyidagi grafik misolida har bir
tugundan boshqa tugunlarga eng qisqa masofalar aniqlandi va har bir yo'lning og'irliklari
hisobga olindi. Ushbu natijalar yordamida Deykstra algoritmining samaradorligini baholash
mumkin, chunki u har bir bosqichda eng qisqa yo'lni tanlaydi va shu orqali optimal yechimga
erishadi.
Kelajakda rivojlantirish imkoniyatlari
: Deykstra algoritmi bugungi kunda ko'plab
sohalarda keng qo'llanilsa-da, uni yanada takomillashtirish uchun ba'zi usullar mavjud:
1.
A algoritmi bilan solishtirish va yaxshilash
*: Deykstra algoritmining samaradorligini
oshirish uchun A* algoritmidan foydalansa bo‘ladi. A* algoritmi heuristik yondashuv orqali
qidiruv maydonini qisqartiradi va maqsad tugunga yo‘lni topishni tezlashtiradi. A* algoritmi
ba'zi hollarda tezroq ishlaydi va katta grafiklarda samarador bo'lishi mumkin.
2.
Ikki tomonlama qidiruvni qo‘llash
: Deykstra algoritmini optimallashtirish uchun
ikki tomonlama qidiruv usulini qo‘llash mumkin. Bu usulda boshlang‘ich va maqsad
tugunlardan bir vaqtda qidiruv boshlanadi, bu esa qidiruv maydonini kamaytiradi va umumiy
hisoblash vaqtini qisqartiradi.
3.
Dinamik dasturlash
: Ba'zi hollarda dinamik dasturlash texnikasidan foydalanib
algoritmning samaradorligini oshirish mumkin, chunki bu usulda ma’lum natijalar qayta
hisoblanmaydi va saqlanib qoladi.
4.
Parallel dasturlash texnikalari
: Katta grafiklarda ko'p masofalarni hisoblash talab
qilinadi. Parallel dasturlash orqali Deykstra algoritmi bir nechta protsessorlar yordamida
tezlashtirilishi mumkin.
Algoritmning ilmiy va amaliy ahamiyati
:
Deykstra algoritmi nafaqat nazariy ahamiyatga ega, balki u ko‘plab amaliy qo‘llanilishlarga
ham ega. Uning ilmiy ahamiyati shundaki, u graf nazariyasi va algoritmlar sohasida eng qisqa
yo‘lni topish masalalarini yechishda asosiy vositalardan biri hisoblanadi.
Algoritmning amaliy ahamiyati quyidagi sohalarda namoyon bo‘ladi:
Transport va logistika
: Yo'nalishlarni optimallashtirish va eng qisqa yo'llarni
aniqlash orqali yuk tashish va yo'lovchi transporti tizimlari samaradorligini oshirishga
yordam beradi.
Telekommunikatsiya va tarmoqlar
: Ma’lumotlarni uzatishda tarmoqdan
foydalanishni optimallashtiradi, tarmoqlarda eng qisqa yo‘l orqali paketlarni uzatishda
samaradorlikni oshiradi.
29
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
Shahar boshqaruvi va GPS tizimlari
: Yo‘llarni aniqlash va yo‘nalishlarni
optimallashtirishda Deykstra algoritmi GPS texnologiyalari bilan birga ishlatiladi, bu esa
harakatlanish vaqtini va yoqilg‘i sarfini kamaytirishga yordam beradi.
Umuman olganda, Deykstra algoritmi nafaqat grafik nazariyasidagi tadqiqotlarda, balki
kundalik hayotda ham ko‘plab muhim muammolarni yechishda foydali vositadir. Shu bois,
uning nazariy va amaliy ahamiyati nafaqat matematik va kompyuter fanlari doirasida, balki
amaliy hayotda ham keng tan olingan.
Tadqiqotning qisqacha natijasi
: Deykstra algoritmi grafdagi eng qisqa yo‘lni topish
masalalarini yechishda keng qo‘llaniladigan usul bo‘lib, u transport va aloqa tarmoqlarida
yo‘nalishlarni optimallashtirish, tarmoqlardagi ma’lumot uzatishni samarali tashkil etish va
logistika masalalarida qo‘llaniladi. Tadqiqot davomida algoritmning ishlash prinsipi, amaliy
qo‘llanilishi va samaradorligi tahlil qilindi. Bu algoritm, ijobiy og‘irlikli grafiklarda juda aniq
natijalar beradi va hisoblashlarda o‘rtacha samaradorlikni ta’minlaydi. Tadqiqotdan kelib
chiqib, Deykstra algoritmining amaliy ahamiyati katta ekanligi va u bir qancha sohalarda
optimal yechim sifatida foydalanilishi mumkinligi aniqlandi.
Algoritmning kuchli tomonlari
: Deykstra algoritmining bir qator kuchli tomonlari mavjud:
1.
Aniq va samarali yechim
: Algoritm har doim optimal natija beradi, ya’ni ijobiy
og‘irlikli grafiklarda eng qisqa yo‘lni topishda mukammal yechimdir.
2.
Qo‘llanilishi osonligi
: Algoritm tushunarli bo‘lib, kodlash va qo‘llash uchun
murakkablik darajasi past. Ko‘p dasturlash tillarida bu algoritmni osongina amalga oshirish
mumkin.
3.
Transport va tarmoqlarda keng qo‘llanilishi
: Deykstra algoritmi transport, logistika
va aloqa tarmoqlarida keng foydalaniladi, bu esa uning real hayotdagi amaliy ahamiyatini
oshiradi.
4.
Moslashuvchanligi
: Algoritm yo'nalishli va yo'nalishsiz grafiklarda, shuningdek, katta
grafiklarda ham qo'llanishi mumkin, shuningdek, ijobiy og'irlikli grafiklar bilan ishlashda
universal yechim hisoblanadi.
Algoritmning zaif tomonlari
:
Deykstra algoritmi o‘zining afzalliklari bilan birga ayrim cheklovlarga ham ega:
Masala:
1.
Shaharlar
: Tashkent, Samarkand, Bukhara, Khiva, Urgench, Nukus, Fergana, Andijan,
Namangan.
2.
Transport yo‘llarining masofalari (km)
:
o
Tashkent → Samarkand (310 km), Tashkent → Fergana (320 km), Tashkent →
Andijan (370 km).
o
Samarkand → Bukhara (270 km), Samarkand → Fergana (500 km), Samarkand
→ Urgench (800 km).
o
Bukhara → Khiva (450 km), Bukhara → Nukus (600 km).
o
Urgench → Nukus (200 km), Khiva → Nukus (150 km).
o
Andijan → Namangan (70 km), Namangan → Fergana (60 km).
o
Nukus → Fergana (1200 km).
Maqsad
: Tashkent shahridan Nukus shahriga eng qisqa masofani hisoblash.
30
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
Deykstri Algoritmi C# Kodida
using
System;
using
System.Collections.Generic;
using
System.Linq;
class
Program
{
public
static
Dictionary
<
string
,
int
>
Dijkstra
(
Dictionary
<
string
,
Dictionary
<
string
,
int
>>
graph,
string
start)
{
var distances =
new
Dictionary
<
string
,
int
>();
var priorityQueue =
new
SortedDictionary
<
int
,
List
<
string
>>();
var visited =
new
HashSet
<
string
>();
foreach
(var node
in
graph)
distances[node.Key] =
int
.
MaxValue
;
distances[start] =
0
;
priorityQueue[
0
] =
new
List
<
string
> { start };
while
(priorityQueue.Count >
0
)
{
var currentDistance = priorityQueue.
First
().Key;
var currentNode = priorityQueue.
First
().Value[
0
];
priorityQueue.
First
().Value.
RemoveAt
(
0
);
if
(priorityQueue.
First
().Value.Count ==
0
)
priorityQueue.
Remove
(currentDistance);
if
(visited.
Contains
(currentNode))
continue
;
visited.
Add
(currentNode);
foreach
(var neighbor
in
graph[currentNode])
{
int
newDistance = distances[currentNode] + neighbor.Value;
if
(newDistance < distances[neighbor.Key])
{
distances[neighbor.Key] = newDistance;
if
(!priorityQueue.
ContainsKey
(newDistance))
priorityQueue[newDistance] =
new
List
<
string
>();
priorityQueue[newDistance].
Add
(neighbor.Key);
}
}
}
return
distances;
}
31
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
static
void
Main
()
{
var graph =
new
Dictionary
<
string
,
Dictionary
<
string
,
int
>>
{
{
"Tashkent"
,
new
Dictionary
<
string
,
int
> { {
"Samarkand"
,
310
}, {
"Fergana"
,
320
},
{
"Andijan"
,
370
} } },
{
"Samarkand"
,
new
Dictionary
<
string
,
int
> { {
"Bukhara"
,
270
}, {
"Fergana"
,
500
},
{
"Urgench"
,
800
} } },
{
"Bukhara"
,
new
Dictionary
<
string
,
int
> { {
"Khiva"
,
450
}, {
"Nukus"
,
600
} } },
{
"Urgench"
,
new
Dictionary
<
string
,
int
> { {
"Nukus"
,
200
} } },
{
"Khiva"
,
new
Dictionary
<
string
,
int
> { {
"Nukus"
,
150
} } },
{
"Andijan"
,
new
Dictionary
<
string
,
int
> { {
"Namangan"
,
70
} } },
{
"Namangan"
,
new
Dictionary
<
string
,
int
> { {
"Fergana"
,
60
} } },
{
"Nukus"
,
new
Dictionary
<
string
,
int
> { {
"Fergana"
,
1200
} } },
{
"Fergana"
,
new
Dictionary
<
string
,
int
>() }
};
var result =
Dijkstra
(graph,
"Tashkent"
);
Console
.
WriteLine
(
"Eng qisqa yo'l Tashkent dan Nukus gacha: "
+ result[
"Nukus"
] +
"
km"
);
Console
.
WriteLine
(
"Barcha shaharlar orasidagi masofalar:"
);
foreach
(var city
in
result)
{
Console
.
WriteLine
($
"{city.Key}: {city.Value} km"
);
}
}
}
Natija:
Eng qisqa yo'l Tashkent dan Nukus gacha: 960 km
Barcha shaharlar orasidagi masofalar:
Tashkent: 0 km
Samarkand: 310 km
Fergana: 320 km
Andijan: 370 km
Namangan: 440 km
Bukhara: 580 km
Urgench: 1110 km
Khiva: 1030 km
Nukus: 960 km
Kod izohi:
1.
Graf ta'rifi
:
o
Har bir shahar va uning ulanishlari masofalari bilan Dictionary yordamida
belgilangan.
2.
Algoritm ishlash printsipi
:
o
priorityQueue navbati eng kichik masofaga ega bo‘lgan shaharlarga qarab
ishlaydi.
o
Har bir shahar uchun eng qisqa masofa qayta hisoblanadi.
32
YANGI O'ZBEKISTON ILMIY
TADQIQOTLAR JURNALI
www.in-academy.uz
1-JILD, 13-SON (YOʻITJ)
3.
Natijalar
:
o
Tashkent shahridan Nukus shahrigacha bo‘lgan eng qisqa masofa hisoblanadi.
o
Barcha shaharlar orasidagi masofalar ko‘rsatiladi.
Xulosa
Deykstra algoritmi grafda eng qisqa yo‘lni topishda eng samarali va keng qo‘llaniladigan
usullardan biri bo‘lib, uning amaliy va nazariy ahamiyati katta. Tadqiqot davomida
algoritmning ishlash prinsipi, matematik asoslari va uni turli sohalarda qo‘llash imkoniyatlari
batafsil tahlil qilindi. Shuningdek, algoritm transport va logistika, telekommunikatsiya va
tarmoq tizimlaridagi yo‘nalishlarni optimallashtirishda, shahar boshqaruvi va navigatsiya
tizimlarida o‘zining yuqori samaradorligini namoyish etdi.
Foydalanilgan adabiyotlar:
1.
Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs".
Numerische Mathematik
, 1(1), 269-271.
2.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to
Algorithms
(3rd ed.). MIT Press.
3.
Kleinberg, J., & Tardos, É. (2005).
Algorithm Design
. Pearson.
4.
Sedgewick, R., & Wayne, K. (2011).
Algorithms
(4th ed.). Addison-Wesley.
5.
Bellman, R. (1958). "On a Routing Problem".
Quarterly of Applied Mathematics
, 16(1),
87-90.
6.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic
Determination of Minimum Cost Paths".
IEEE Transactions on Systems Science and Cybernetics
,
4(2), 100-107.
7.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993).
Network Flows: Theory, Algorithms,
and Applications
. Prentice Hall.
8.
Moore, E. F. (1957). "The Shortest Path through a Maze".
Proceedings of an
International Symposium on the Theory of Switching
, 285-292.
9.
Tarjan, R. E. (1972). "Depth-First Search and Linear Graph Algorithms".
SIAM Journal
on Computing
, 1(2), 146-160.
10.
Johnson, D. B. (1977). "Efficient Algorithms for Shortest Paths in Sparse Networks".
Journal of the ACM (JACM)
, 24(1), 1-13.
11.
Papadimitriou, C. H., & Steiglitz, K. (1998).
Combinatorial Optimization: Algorithms and
Complexity
. Dover Publications.
12.
Goldberg, A. V., & Harrelson, C. (2005). "Computing the Shortest Path: A* Search Meets
Graph Theory".
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete
Algorithms
, 156-165.
13.
Edsger, D. W. (1976).
Selected Writings on Computing: A Personal Perspective
. Springer.
14.
Bertsekas, D. P. (1998).
Network Optimization: Continuous and Discrete Models
. Athena
Scientific.
15.
Delling, D., Sanders, P., Schultes, D., & Wagner, D. (2009). "Engineering Route Planning
Algorithms".
Algorithmics of Large and Complex Networks
, 117-139.
