299
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
SHAHAR JAMOAT TRANSPORTI YO‘NALISHLARINI TAKOMILLASHTIRISHDA
DIJKSTRA ALGORITMINING AHAMIYATI (FARG‘ONA SHAHRI MISOLIDA)
Xametov Zamirbek Muxtorovich
Farg‘ona davlat texnika universiteti, “Transport vositalari muhandisligi” kafedrasi mudiri.
Tel: (99)999-92-66.
Gmail:
zamir311384@mail.ru, Xametov.Z@fstu.uz.
Karimov Javohir Shuhratovich
Farg‘ona davlat texnika universiteti, “Transport vositalari muhandisligi” kafedrasi 1-bosqich
doktoranti.
Tel: (93)337-44-33
https://doi.org/10.5281/zenodo.17159187
Annotatsiya.
Shahar jamoat transporti tizimida yo‘lovchilar oqimini samarali
boshqarish va marshrutlarni optimallashtirish dolzarb masalalardan biridir. Ushbu tadqiqotda
Dijkstra algoritmining nazariy asoslari va graflar nazariyasidagi o‘rni tahlil qilinib, uning
avtobus yo‘nalishlarini rejalashtirishdagi qo‘llanish imkoniyatlari ko‘rib chiqildi. Farg‘ona
shahri transport ma’lumotlari asosida algoritmning amaliy qo‘llanilishi o‘rganilib,
foydalanuvchilar uchun eng qisqa marshrutni tanlashga yordam beruvchi konseptual model
ishlab chiqildi. Tadqiqot natijalari algoritmning transport tizimida samaradorlikni oshirishdagi
ahamiyatini ko‘rsatdi.
Kalit so‘zlar:
shahar jamoat transporti, transport logistikasi, Dijkstra algoritmi, eng
qisqa yo‘l, Farg‘ona shahri.
Аннотация.
Эффективное управление пассажиропотоком и оптимизация
маршрутов городского общественного транспорта является актуальной задачей. В
исследовании проанализированы теоретические основы алгоритма Дейкстры и его
применение при планировании автобусных маршрутов. На основе данных транспортной
системы города Ферганы рассмотрены практические возможности использования
алгоритма и предложена концептуальная модель для определения кратчайшего
маршрута. Результаты показали, что использование алгоритма способствует
повышению эффективности транспортной системы.
Ключевые слова:
городской общественный транспорт, транспортная логистика,
алгоритм Дейкстры, кратчайший путь, город Фергана.
Abstract.
Efficient passenger flow management and route optimization in urban public
transport remain pressing issues. This study analyzes the theoretical foundations of Dijkstra’s
algorithm and its application to bus route planning. Using data from Fergana city’s transport
system, practical opportunities of applying the algorithm were examined, and a conceptual
model for identifying the shortest route was developed. The findings demonstrate the algorithm’s
significance in improving urban transport efficiency.
Keywords:
urban public transport, transport logistics, Dijkstra’s algorithm, shortest
path, Fergana city.
Kirish
Eng qisqa yo‘l muammosi (Shortest Path Problem, SPP) graflar nazariyasining klassik
masalalaridan biri bo‘lib, transport tizimlarini tashkil etishda, ishlab chiqarish jarayonlarini
optimallashtirishda, logistika va boshqaruv sohalarida keng qo‘llaniladi[2],[7]. Ushbu muammo
shahar jamoat transporti tizimini samarali boshqarish va yo‘lovchilarga qulay xizmat ko‘rsatish
uchun alohida ahamiyat kasb etadi.
300
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
Bugungi kunda aholi sonining ortishi va shaharlar transport tizimining murakkablashuvi
natijasida jamoat transportida optimal marshrutlarni aniqlash tobora dolzarb masalaga
aylanmoqda. Yo‘lovchilarning vaqtini tejash, bekatlar orasida ortiqcha yurishni kamaytirish
hamda transport oqimini muvozanatlashtirish uchun matematik va algoritmik yondashuvlarga
asoslangan yechimlardan foydalanish talab etiladi[8],[9]. Shu nuqtayi nazardan, 1959-yilda
Edsger Dijkstra tomonidan ishlab chiqilgan Dijkstra algoritmi eng qisqa yo‘l muammosini
samarali yechishda keng qo‘llaniladigan va amaliy ahamiyatga ega bo‘lgan algoritmlardan
biridir[1]. Ushbu algoritm yordamida shahar avtobus yo‘nalishlari tarmog‘ida boshlang‘ich
bekatdan maqsad bekatigacha eng qisqa va qulay yo‘lni aniqlash mumkin.
Asosiy qism
Eng qisqa yo‘l muammosi va algoritmlar.
Eng qisqa yo‘l muammosi kundalik hayotda
ham, shahar transport tizimida ham katta amaliy ahamiyatga ega. Masalan, agar Farg‘ona
shahrida yo‘lovchi A nuqtadan B nuqtaga borishni istasa, u nafaqat masofaviy jihatdan, balki
vaqt sarfi va o‘tish (transfer) soni jihatidan ham eng maqbul yo‘lni topishga intiladi. Bu jarayon
nafaqat yo‘lovchilar uchun qulaylik yaratadi, balki butun shahar transport tizimining
samaradorligini ham oshiradi[8]. Shuningdek, yirik infratuzilma loyihalarida, xususan, Farg‘ona
viloyatida yangi temiryo‘l yoki avtobus yo‘nalishlarini tashkil etishda ham ushbu muammo
dolzarbdir. Qurilish xarajatlarini kamaytirish, aholi yashash hududlariga qulaylik yaratish va
iqtisodiy samaradorlikni ta’minlash eng qisqa yo‘l muammosini hisobga olishni talab qiladi.Eng
qisqa yo‘l muammolarini yechish uchun ko‘plab kompyuter olimlari turli algoritmlar ishlab
chiqdilar.
Dijkstra algoritmi
, 1959-yilda Dijkstra tomonidan taklif qilingan bo‘lib, eng qisqa
yo‘lni topish algoritmlaridan biridir. U kengaytirilgan qidiruv (Breadth-first search) va “ochko‘z
algoritm” (greedy algorithm) printsiplariga asoslanadi [1],[2]. Boshqacha qilib aytganda, u
barcha tugunlarni tekshiradi, har bir bosqichda optimal natijani tanlaydi va barcha tugunlar
ko‘rib chiqilgandan so‘ng yakuniy natijani beradi.
Bellman–Ford algoritmi
ham Dijkstra
algoritmiga o‘xshash bo‘lib, eng qisqa yo‘l muammosini hal etishda qo‘llanadi. U “relaksatsiya”
printsipiga asoslanadi va har bir qirra ushbu jarayonni |V|-1 (tugunlar sonidan 1 ta kam) marta
bajaradi [3][4]. Bu algoritm ko‘proq vaqt talab qilsa-da, qo‘llanishda yanada moslashuvchanlikni
ta’minlaydi. Yana bir algoritm -
Floyd–Warshall algoritmi
bo‘lib, u ham eng qisqa yo‘l
muammosini hal etishda qo‘llanadi. Bu algoritm ixtiyoriy ikkita tugun orasidagi eng qisqa yo‘lni
topishga qaratilgan va dinamik dasturlash printsipiga asoslanadi [5][6].
Dijkstra algoritmining ishlash prinsipi.
Yuqorida keltirilgan turli algoritmlar ichida
Dijkstra algoritmi
eng klassik va keng qo‘llaniladigan algoritm hisoblanadi[1],[7]. U vaqt
murakkabligi jihatidan samarali bo‘lib, quyidagicha ifodalanadi:
O(|E|+|V|log|V|)
Bu yerda |V| – tugunlar soni, |E| – qirralar sonini anglatadi.
Dijkstra algoritmi nafaqat boshlang‘ich tugundan yakuniy tugungacha bo‘lgan eng qisqa
yo‘lni, balki boshlang‘ich tugundan barcha tugunlargacha bo‘lgan eng qisqa yo‘llarni ham
aniqlab beradi. Algoritmning ishlash tartibi quyidagicha:
1.
Har bir tugunga ikki qiymat biriktiriladi:
o
d
j
– boshlang‘ich tugundan j-tugungacha bo‘lgan eng qisqa masofa,
o
p
j
– shu yo‘ldagi oldingi tugun.
2.
Boshlang‘ich tugun masofasi 0 qilib belgilanadi, qolganlari esa ∞ deb olinadi.
3.
Har safar eng kichik masofaga ega tugun tanlanadi va unga bog‘langan qo‘shni
tugunlarning masofasi yangilanadi.
301
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
4.
Barcha tugunlar belgilangach, algoritm yakunlanadi.
Misol.
Quyida berilgan grafda quyidagi qirralar (yo‘llar) va ularning og‘irliklari
(masofalari) keltirilgan:
Qirralar va ularning og‘irliklari:
A → B: 4, A → C: 5, B → D: 9, B → C: 11, C → E: 3, D → E: 13, D → F: 2, E → F: 6
Vazifa: A tugundan barcha boshqa tugunlargacha eng qisqa yo‘lni topish.
1-bosqich. Boshlang‘ich qiymatlar:
Masofalar:
A = 0, B = ∞, C = ∞, D = ∞, E = ∞, F = ∞
Ko‘rilmagan tugunlar majmuasi: {A, B, C, D, E, F}
Joriy tugun: A
2-bosqich. A tugunining qo‘shnilarini tekshirish:
B uchun masofa yangilanadi: Distance[B] = 0 + 4 = 4
C uchun masofa yangilanadi: Distance[C] = 0 + 5 = 5
Masofalar:
A=0, B=4, C=5, D=∞, E=∞, F=∞
3-bosqich. A tugunini ko‘rilgan deb belgilash:
Ko‘rilmagan tugunlar: {B, C, D, E, F}
4-bosqich. Keyingi joriy tugun sifatida B tanlanadi:
Joriy tugun: B
B qo‘shnilari:
D uchun masofa: Distance[D] = 4 + 9 = 13
C uchun masofa: Distance[C] = min(5, 4 + 11) = 5 (o‘zgarishsiz qoladi)
Masofalar:
A=0, B=4, C=5, D=13, E=∞, F=∞
5-bosqich. B tuguni ko‘rilgan deb belgilanadi:
Ko‘rilmagan tugunlar: {C, D, E, F}
6-bosqich. Keyingi joriy tugun sifatida C tanlanadi:
Joriy tugun: C
C qo‘shnilari:
E uchun masofa: Distance[E] = 5 + 3 = 8
Masofalar:
A=0, B=4, C=5, D=13, E=8, F=∞
7-bosqich. C tuguni ko‘rilgan deb belgilanadi:
Ko‘rilmagan tugunlar: {D, E, F}
8-bosqich. Keyingi joriy tugun sifatida E tanlanadi:
302
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
Joriy tugun: E
E qo‘shnilari:
F uchun masofa: Distance[F] = 8 + 6 = 14
Masofalar:
A=0, B=4, C=5, D=13, E=8, F=14
9-bosqich. E tuguni ko‘rilgan deb belgilanadi:
Ko‘rilmagan tugunlar: {D, F}
10-bosqich. Keyingi joriy tugun sifatida D tanlanadi:
Joriy tugun: D
D qo‘shnilari:
F uchun masofa: Distance[F] = min(14, 13 + 2) = 14 (o‘zgarishsiz qoladi)
Masofalar:
A=0, B=4, C=5, D=13, E=8, F=14
11-bosqich. D tuguni ko‘rilgan deb belgilanadi:
Ko‘rilmagan tugunlar: {F}
12-bosqich. Keyingi joriy tugun sifatida F tanlanadi:
Joriy tugun: F
F ham ko‘rilgan deb belgilanadi.
Ko‘rilmagan tugunlar: {}
Shu bilan barcha tugunlar tekshirildi. Eng qisqa masofalar quyidagicha:
A → B: 4, A → C: 5, A → D: 13, A → E: 8, A → F: 14
Dijkstra algoritmini Farg’ona shahri jamoat transporti tizimida qo‘llash zarurati.
Shahar jamoat transporti tizimini samarali tashkil etishda marshrutlarni tanlash, eng
maqbul yo‘nalishlarni belgilash va yo‘lovchilar oqimini optimallashtirish muhim ahamiyat kasb
etadi. Ayniqsa, yo‘lovchilar bir manzildan ikkinchi manzilga minimal vaqt va masofa bilan yetib
olishlari transport logistikasining asosiy vazifalaridan biridir. Ushbu jarayonni matematik
modellashtirish uchun graf nazariyasi vositalaridan foydalaniladi. Graf nazariyasida shahar
bekatlari tugunlar (vertex), ularni bog‘lovchi transport yo‘llari esa qirralar (edge) sifatida
qaraladi.
Dijkstra algoritmi esa bunday grafda ma’lum boshlang‘ich tugundan boshqa barcha
tugunlargacha eng qisqa yo‘lni topishga mo‘ljallangan algoritmdir. Algoritm har bir bosqichda
minimal masofa tanlash tamoyiliga asoslanadi va shu jihati bilan jamoat transportida
yo‘lovchilar uchun optimal marshrutlarni aniqlashda samarali qo‘llaniladi[2],[7].
Farg‘ona shahri o‘zining zich aholi joylashuvi, iqtisodiy faolligi va transport oqimining
yuqoriligi bilan ajralib turadi. Shaharda avtobus va marshrutka asosiy tashish tizimini tashkil
qiladi. Shu sababli, mavjud marshrutlar ichida eng qisqa yo‘lni aniqlash ham yo‘lovchilar, ham
transport operatorlari uchun muhim hisoblanadi. Masalan, yo‘lovchi “Markaziy bekat”dan
“Temir yo‘l vokzali”ga yetib borishi uchun bir nechta marshrutlardan foydalanishi mumkin.
Lekin ularning har biri vaqt va masofa bo‘yicha turlicha. Shunday sharoitda Dijkstra
algoritmi orqali eng maqbul yo‘l aniqlanadi.
Endi Markaziy bekatdan (A) Temir yo‘l vokzaligacha (E) eng qisqa yo‘lni Dijkstra
algoritmi asosida topamiz.
A = Markaziy bekat (Markaziy avtovokzal), B = Univermag, C = Avtoshohbekat, D =
Qo‘qon yo‘li bekati, E = Temir yo‘l vokzali.
Qirralar va og‘irliklar (masofalar, km):
303
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
A – B : 2.5, A – C : 3.0, B – D : 1.8, B – E : 2.0, C – D : 2.2, D – E : 2.0
1-bosqich. Boshlang‘ich qiymatlar:
A = 0, B = ∞, C = ∞, D = ∞, E = ∞
2-bosqich. A tugunining qo‘shnilari:
B: 0 + 2.5 = 2.5
C: 0 + 3.0 = 3.0
Masofalar: A=0, B=2.5, C=3.0, D=∞, E=∞
3-bosqich. Eng kichik masofa – B (2.5). B tugunidan qo‘shnilar:
D: 2.5 + 1.8 = 4.3
E: 2.5 + 2.0 =
4.5
Masofalar: A=0, B=2.5, C=3.0, D=4.3, E=4.5
4-bosqich. Keyingi tugun – C (3.0). C qo‘shnilari:
D: min(4.3, 3.0+2.2=5.2) → 4.3 (o‘zgarishsiz)
5-bosqich. Keyingi tugun – D (4.3). D qo‘shnilari:
E: min(4.5, 4.3+2.0=6.3) → 4.5 (o‘zgarishsiz)
6-bosqich. Yakuniy natija:
A → B → E =
4.5 km
– eng qisqa yo‘l.
Shu tariqa, yo‘lovchi uchun eng qulay marshrut
“Markaziy bekat → Univermag →
Temir yo‘l vokzali”
yo‘nalishi bo‘ldi.
Xulosa
Tadqiqot davomida shahar jamoat transporti tizimida eng qisqa yo‘l muammosini
yechishga oid nazariy va amaliy yondashuvlar o‘rganildi hamda Dijkstra algoritmining
samaradorligi asoslab berildi. Graflar nazariyasi vositalaridan foydalanish orqali shahar bekatlari
va ularni bog‘lovchi transport yo‘llari modellashtirildi, Farg‘ona shahri jamoat transporti tizimi
misolida algoritmning amaliy ahamiyati tahlil qilindi.Olib borilgan hisob-kitoblarga ko‘ra,
“Markaziy bekat – Univermag – Temir yo‘l vokzali” yo‘nalishi eng qisqa marshrut sifatida
aniqlanib, umumiy masofa 4,5 kmni tashkil etdi. Ushbu natija Dijkstra algoritmining real
transport sharoitlarida samarali qo‘llanishi mumkinligini tasdiqlaydi.
Xulosa qilib aytganda, Dijkstra algoritmini jamoat transporti yo‘nalishlarini
takomillashtirishda qo‘llash yo‘lovchilar vaqtini tejash, transport oqimini muvozanatlashtirish va
xizmat ko‘rsatish sifatini oshirish imkonini beradi. Shuningdek, ushbu yondashuv transport
logistikasining ilmiy asoslangan yechimlarini ishlab chiqishda hamda “aqlli shahar” konsepsiyasi
doirasida raqamli tizimlarni joriy etishda muhim amaliy ahamiyat kasb etadi.
Adabiyotlar ro‘yhati
1.
Dijkstra, E. W. (1959).
A note on two problems in connexion with graphs
. Numerische
Mathematik, 1, 269–271.
2.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to
Algorithms
(3rd ed.). MIT Press.
3.
Bellman, R. (1958).
On a routing problem
. Quarterly of Applied Mathematics, 16(1), 87–
90.
4.
Ford, L. R., & Fulkerson, D. R. (1962).
Flows in Networks
. Princeton University Press.
5.
Floyd, R. W. (1962).
Algorithm 97: Shortest path
. Communications of the ACM, 5(6),
345.
6.
Warshall, S. (1962).
A theorem on Boolean matrices
. Journal of the ACM, 9(1), 11–12.
304
ResearchBib IF - 11.01, ISSN: 3030-3753, Volume 2 Issue 9
7.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993).
Network flows: Theory, algorithms,
and applications
. Prentice Hall.
8.
G‘aniev, S. (2020). Transport logistikasida zamonaviy yondashuvlar.
O‘zbekiston
transport va kommunikatsiya jurnali
, 4(2), 45–52.
