ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
400
2181-3187
GRAFDA ENG QISQA YOLNI TOPISH. ALGORITMLAR VA
YECHIMLAR
Toshboltayev Faxriddin O‘rinboyevich
FarDU Axborot texnologiyalari
kafedrasi katta o‘qituvchisi(PhD)
Abidova Nafosatxon Nozimjon qizi
Farg‘ona davlat universiteti 3-kurs talabasi
Annotatsiya: Ushbu maqolada graf nazariyasining muhim muammolaridan biri
bo‘lgan eng qisqa yo‘lni topish masalasi ko‘rib chiqiladi. Dijkstra, Bellman-Ford,
Floyd-Warshall va A* algoritmlari tahlil qilinib, ularning ishlash prinsipi, vaqt
murakkabligi va qo‘llanilish sohalari taqqoslanadi. Har bir algoritmning afzalliklari va
cheklovlari haqidagi ma’lumotlar asosida konkret masalalarga mos yechimlar taklif
etiladi.
Аннотация: В данной статье рассматривается одна из ключевых задач
теории графов — нахождение кратчайшего пути. Анализируются алгоритмы
Дейкстры, Беллмана-Форда, Флойда-Уоршелла и A*, описываются принципы их
работы, временная сложность и области применения. На основе сравнительного
анализа предложены подходящие решения для различных типов графов и задач.
Abstract: This article explores one of the fundamental problems in graph theory
— finding the shortest path. Algorithms such as Dijkstra, Bellman-Ford, Floyd-
Warshall, and A* are analyzed, including their working principles, time complexity,
and application areas. Based on a comparative study, suitable solutions are proposed
for different types of graphs and problem contexts.
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
401
2181-3187
Kalit so‘zlar:Graf, eng qisqa yo‘l, Dijkstra algoritmi, Bellman-Ford, Floyd-
Warshall, A* algoritmi, yo‘l topish, murakkablik.
Kirish
Graf nazariyasi matematika va informatikaning eng muhim va amaliy ahamiyatga
ega bo‘lgan sohalaridan biridir. Uning asosiy elementlari — tugunlar (nuqtalar) va
ularni bog‘lovchi qirralar (yo‘llar) — orqali turli real hayotiy tizimlar, masalan,
transport tarmoqlari, ijtimoiy tarmoqlar, aloqa tizimlari, yo‘l harakati, internet
marshrutlash va logistika tizimlari modellashtiriladi. Graflarda eng ko‘p uchraydigan
va dolzarb masalalardan biri — bu ikki tugun orasidagi eng qisqa yo‘lni topish
muammosidir.
Eng qisqa yo‘lni topish masalasi — berilgan boshlang‘ich tugundan boshqa
tugungacha bo‘lgan yo‘llar orasidan umumiy yo‘l uzunligi (yoki xarajati) eng kam
bo‘lganini aniqlashdan iborat. Ushbu masala faqat nazariy emas, balki amaliy jihatdan
ham katta ahamiyatga ega. Masalan, GPS navigatsiyada eng qisqa yo‘lni aniqlash,
internet paketlarini uzatishda optimal marshrutni belgilash, robot texnikasida
to‘siqlardan chetlab o‘tish uchun yo‘l rejalashtirish kabi sohalarda qo‘llaniladi.
Muammoning yechimi grafning tuzilishi va og‘irliklar (masofa, vaqt, xarajat)
taqsimotiga bog‘liq bo‘lib, har xil holatlar uchun turli algoritmlar qo‘llaniladi.
Masalan, Dijkstra algoritmi ijobiy og‘irlikli grafda eng mashhur va samarali yondashuv
bo‘lsa, Bellman-Ford algoritmi manfiy og‘irliklar mavjud bo‘lgan holatlarda
qo‘llanilishi mumkin. Floyd-Warshall algoritmi esa barcha tugunlar orasidagi eng
qisqa yo‘llarni bir vaqtda hisoblab berish imkonini beradi. Shuningdek, sun’iy intellekt
yondashuvlariga yaqin bo‘lgan A* (A-star) algoritmi heuristikani qo‘llab, yo‘l
topishda muayyan ustunliklarga ega
Ushbu maqolada yuqorida nomi tilga olingan asosiy algoritmlar keng tahlil
qilinadi, ularning ishlash prinsiplari, afzallik va kamchiliklari, vaqt murakkabligi
ko‘rib chiqiladi hamda real masalalarga qanday mos tushishi o‘rganiladi. Bundan
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
402
2181-3187
maqsad — turli graf strukturalari va masala talablari uchun eng samarali algoritmni
tanlash mezonlarini shakllantirishdir.
Asosiy qism
Grafda eng qisqa yo‘lni topish masalasi turli holatlar uchun turlicha
yondashuvlarni talab qiladi. Bu bo‘limda eng mashhur algoritmlar — Dijkstra,
Bellman-Ford, Floyd-Warshall va A* (A-star) algoritmlarining ishlash mexanizmi,
afzalliklari, cheklovlari va amaliy qo‘llanilish sohalari yoritiladi.
1. Dijkstra algoritmi
Dijkstra algoritmi 1956-yilda Edsger Dijkstra tomonidan ishlab chiqilgan va u
ijobiy og‘irlikli grafda bitta boshlang‘ich tugundan qolgan barcha tugungacha eng
qisqa yo‘lni topish uchun mo‘ljallangan.
Ishlash prinsipi:
Har bir tugunga cheksiz masofa belgilanadi, boshlang‘ich tugunga 0 masofa
qo‘yiladi.
Har gal eng kichik masofali tugun tanlanadi va uning qo‘shni tugunlariga masofa
yangilanadi.
Tizim tugunlar tugamaguncha yoki kerakli manzilga yetmaguncha davom etadi.
Afzalliklari:
Tez va samarali.
Ijobiy og‘irlikli graf uchun optimal natija beradi.
Cheklovlari:
Manfiy og‘irliklar bilan ishlay olmaydi.
Murakkablik: O(|E| + |V| log |V|) — (E – qirralar soni, V – tugunlar soni)
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
403
2181-3187
2. Bellman-Ford algoritmi
Bellman-Ford algoritmi manfiy og‘irlikli graf uchun eng qisqa yo‘lni topishda
qo‘llaniladi. Bu algoritm Dijkstra’dan farqli o‘laroq, barcha qirralar orqali maksimal
|V|-1 marta takroriy tekshiruv o‘tkazadi.
Afzalliklari:
Manfiy og‘irlikli graf bilan ishlay oladi.
Eng qisqa yo‘l yo‘qligini (masalan, manfiy sikl) aniqlay oladi.
Cheklovlari:
Ishlash tezligi pastroq.
Katta graflarda sekin ishlaydi.
Murakkablik: O(|V| × |E|)
3. Floyd-Warshall algoritmi
Floyd-Warshall algoritmi — barcha tugunlar juftligi orasidagi eng qisqa yo‘lni
topish uchun ishlatiladi. Dinamik dasturlashga asoslangan bo‘lib, graf og‘irlik
matritsasini qayta-qayta yangilash orqali yakuniy natijani beradi.
Afzalliklari:
Har qanday og‘irlikdagi grafda ishlaydi (manfiy og‘irlik — lekin sikl bo‘lmasligi
sharti bilan).
Barcha tugunlar orasidagi yo‘llar bir vaqtda hisoblanadi.
Cheklovlari:
Katta o‘lchamli graf uchun xotira va vaqt jihatdan juda talabchan.
Murakkablik: O(|V|³)
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
404
2181-3187
4. A* (A-star) algoritmi
A* algoritmi — heuristikaga asoslangan algoritm bo‘lib, u eng qisqa yo‘lni
aniqroq va tezroq topishga intiladi. Bu algoritm odatda interaktiv muhitlarda (masalan,
o‘yinlar, GPS tizimlari) ishlatiladi.
Ishlash prinsipi:
Har bir tugun uchun g(n) — hozirgi tugungacha bo‘lgan xarajat, h(n) — taxminiy
qolgan masofa hisoblanadi.
f(n) = g(n) + h(n) qiymat bo‘yicha eng kichik tugun tanlab olinadi.
Afzalliklari:
Tez ishlaydi.
Ancha aniqlik bilan kerakli yo‘lni topadi (agar heuristika to‘g‘ri tanlansa).
Cheklovlari:
Heuristika noto‘g‘ri bo‘lsa, noto‘g‘ri natija chiqishi mumkin.
Manfiy og‘irliklarda ishlamaydi.
Murakkablik: Eng yomon holatda Dijkstra’ga teng yoki sekinroq, lekin amalda
tezroq ishlaydi.
Algoritm
Manfiy
og‘irlik
Har doim
optimal
Murakkablik
Foydalanish
holati
Dijkstra
Yo‘q
Ha
O(
E
Bellman-
Ford
Ha
Ha
O(
V
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
405
2181-3187
Algoritm
Manfiy
og‘irlik
Har doim
optimal
Murakkablik
Foydalanish
holati
Floyd-
Warshall
Qisman
Ha
O(
V
A*
Yo‘q
Ha
(heuristika
to‘g‘ri bo‘lsa)
O(
E
Xulosa
Grafda eng qisqa yo‘lni topish masalasi — nafaqat nazariy informatika, balki
amaliy muammolarni hal qilishda ham muhim o‘rin tutadi. Mazkur maqolada eng keng
tarqalgan algoritmlar — Dijkstra, Bellman-Ford, Floyd-Warshall va A* algoritmlari
ko‘rib chiqildi. Har bir algoritmning ishlash mexanizmi, murakkabligi va qo‘llanilish
sohasi batafsil tahlil qilindi.
Tahlillardan ko‘rinadiki:
Dijkstra algoritmi ijobiy og‘irlikli grafda tez va samarali yechim beradi;
Bellman-Ford algoritmi manfiy og‘irliklar mavjud bo‘lgan graflarda ishonchli
hisoblanadi;
Floyd-Warshall algoritmi esa barcha tugun juftliklari orasidagi eng qisqa yo‘lni
hisoblashda foydali;
A* algoritmi esa heuristikaga asoslangan holda interaktiv va real vaqt tizimlarida
yuqori natijalar beradi.
Demak, eng qisqa yo‘lni topish uchun yagona universal algoritm mavjud emas.
Har bir holatda grafning xususiyatlari, resurslar cheklovi va amaliy maqsadlar asosida
eng mos algoritm tanlanishi kerak. Kelgusida sun’iy intellekt yondashuvlarini
ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ
https://scientific-jl.org/obr
Выпуск журнала №-69
Часть–4_ Мая –2025
406
2181-3187
chuqurroq integratsiyalash orqali bu algoritmlarning samaradorligini oshirish
imkoniyati mavjud.
Foydalanilgan adabiyotlar
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction
to
Algorithms
(3rd
ed.).
MIT
Press.
(Mashhur algoritmlar haqidagi asosiy manba; Dijkstra, Bellman-Ford, Floyd-Warshall
kabilarni o‘z ichiga oladi.)
Dasgupta,
S.,
Papadimitriou,
C.,
&
Vazirani,
U.
(2006).
Algorithms.
McGraw-Hill.
(Oddiy tilda tushuntirilgan algoritmlar kitobi, talabalarga mo‘ljallangan.)
Абдусаматов,
К.
(2012).
Algoritmlar va ma'lumotlar tuzilmalari. Toshkent: O‘zbekiston Milliy universiteti
nashriyoti.
(O‘zbek tilida algoritmlar asosida yozilgan mahalliy manba.)
GeeksforGeeks.
(n.d.).
https://www.geeksforgeeks.org/shortest-path-algorithms
(Onlayn interaktiv o‘rgatuvchi maqola va kod misollar.)
Visualgo.net
–
Graph
Algorithms
Visualizer.
https://visualgo.net/en
(Algoritmlarning vizualizatsiyasi uchun onlayn platforma.)
