JOURNAL OF NEW CENTURY INNOVATIONS
Volume–77_Issue-2_May-2025
268
268
FLOYD-UORSHAL ALGORITMI
Yusupov Mirsaid Abdulaziz o’g’li
Farg’ona Davlat Universiteti
Amaliy matematika va informatika kafedrasi o’qituvchisi
Fargʻona davlat universiteti 2-bosqich talabasi
Rahimova Zarifaxon Shuxratjon qizi
Anotatsiya
: Ushbu maqolada Floyd-Uorshal algoritmi va uning yo‘l uzunliklarini
hisoblashdagi qo‘llanilishi haqida so‘z boradi. Algoritm barcha juft cho‘qqilar
orasidagi eng qisqa yo‘llarni aniqlashda ishlatiladi va graf nazariyasida muhim o‘rin
tutadi. Dasturiy ta'minotda, marshrutlashda va boshqa ko‘plab sohalarda keng
qo‘llaniladi.
Kalit so‘zlar
: Floyd-Uorshal algoritmi, eng qisqa yo‘l, graf, yo‘l matritsasi,
algoritm, dinamik dasturlash.
Аннотация:
В данной статье рассматривается алгоритм Флойда-Уоршелла
и его применение для нахождения кратчайших путей между всеми парами
вершин в графе. Алгоритм широко используется в теории графов,
программировании, сетевой маршрутизации и других областях.
Ключевые слова:
алгоритм Флойда-Уоршелла, кратчайший путь, граф,
матрица путей, алгоритм, динамическое программирование.
Abstract:
This paper discusses the Floyd-Warshall algorithm and its application
in finding the shortest paths between all pairs of vertices in a graph. The algorithm
plays a significant role in graph theory and is widely used in programming, routing,
and various computational fields.
Keywords
: Floyd-Warshall algorithm, shortest path, graph, path matrix,
algorithm, dynamic programming.
KIRISH
Axborot texnologiyalarining jadal rivojlanishi va katta hajmdagi ma’lumotlar
bilan ishlash zarurati tufayli graflar nazariyasi va unga asoslangan algoritmlar
informatikada muhim ahamiyat kasb etmoqda. Ayniqsa, marshrutlash, tarmoq tahlili,
transport tizimlari, sun’iy intellekt, geoinformatsion tizimlar kabi sohalarda graflar
orqali model qurish keng qo‘llanilmoqda. Bunday hollarda grafikdagi har bir
cho‘qqilar juftligi orasidagi eng qisqa yo‘llarni aniqlash muammosi tez-tez uchraydi
va bu muammoni samarali hal etish uchun maxsus algoritmlarga ehtiyoj tug‘iladi.
JOURNAL OF NEW CENTURY INNOVATIONS
Volume–77_Issue-2_May-2025
269
269
Eng qisqa yo‘lni topish masalasi algoritmshunoslikda klassik muammolardan biri
hisoblanadi. Ushbu muammo, odatda, yo‘nalgan yoki yo‘nalmagan, og‘irliklar
(vaznlar) bilan berilgan graf asosida hal qilinadi. Dijkstra algoritmi, Bellman-Ford
algoritmi kabi yondashuvlar ma’lum bir boshlang‘ich cho‘qqidan qolgan barcha
cho‘qqilargacha bo‘lgan eng qisqa yo‘lni topishga mo‘ljallangan bo‘lsa,
Floyd-
Uorshal algoritmi
butun graf bo‘yicha barcha juftliklar orasidagi eng qisqa yo‘llarni
aniqlash imkonini beradi. Bu esa uni yanada umumiyroq va ko‘p hollarda samaraliroq
yechimga aylantiradi.
Floyd-Uorshal algoritmi 1962-yilda Robert Floyd va Stiven Uorshal tomonidan
ishlab chiqilgan bo‘lib, u dinamik dasturlash prinsiplariga asoslanadi. Algoritm iterativ
tarzda ishlaydi: dastlab to‘g‘ridan-to‘g‘ri bog‘langan cho‘qqilar orasidagi masofalar
aniqlanadi, so‘ngra oraliq cho‘qqilar orqali borish imkoniyatlari hisobga olinib, har bir
bosqichda eng qisqa yo‘llar yangilanib boriladi. Natijada, ma’lum bir oraliq cho‘qqilar
orqali o‘tuvchi yo‘llar bevosita yo‘ldan qisqaroq bo‘lsa, u avtomatik ravishda
tanlanadi.
Algoritmning hisoblash murakkabligi O(n3)O(n^3)O(n3) bo‘lib, bu uni o‘rta
hajmli graflar uchun amaliy jihatdan foydali qiladi. Xususan, bu algoritm salbiy
og‘irliklarga ega grafda ham ishlaydi (lekin manfiy sikllar mavjud bo‘lmasligi sharti
bilan). Bundan tashqari, algoritm yo‘llar mavjudligini aniqlash, tranzitiv yopilishni
hisoblash, va bog‘langanlikni tahlil qilish kabi muammolarda ham qo‘llaniladi.
Mazkur ishda Floyd-Uorshal algoritmining nazariy asoslari, ishlash mexanizmi,
algoritmik ifodasi, murakkabligi tahlili hamda amaliy misollar orqali uning
qo‘llanilishi atroflicha ko‘rib chiqiladi. Shuningdek, algoritmni Python dasturlash tili
yordamida amalga oshirish va natijalarni tahlil qilish bo‘yicha misollar ham keltiriladi.
Foydalanilgan adabiyotlar:
1.
"Network Flows: Theory, Algorithms, and Applications" - Ravindra K. Ahuja,
Thomas L. Magnanti, James B. Orlin
2.
"Optimization Methods in Operations Research and Systems Analysis" - A.
Ravindran, D. T. Phillips, J. J. Solberg
3.
"Introduction to Operations Research" - Frederick S. Hillier, Gerald J. Lieberman
4.
Operations Research: Applications and Algorithms" - Wayne L. Winston
5.
5. Mykel J. Kochenderfer. Tim A. Wheeler. Algorithms for Optimization.
Published by The MIT Press., in London, England. 2019. – 500 p.
6.
6. Рафгарден Тим. Совершенный алгоритм. Графовые алгоритмы и
структуры данных. – СПб.: Питер, 2019. - 256 с.
7.
7.
Ахо Альфред В., Ульман Джеффри Д., Хопкрофт Джон Э.
Структуры данных и алгоритмы. – М.: Вильямс, 2018. – 400 с.
8.
8. Дж.Хайнеман, Г.Поллис, С.Стэнли. Алгоритмы. Справочник с примерами
на С, C++, Java и Python, 2-е изд.: Пер. с англ. — СпБ.: ООО "Альфа-книга",
2017. — 432 с.
JOURNAL OF NEW CENTURY INNOVATIONS
Volume–77_Issue-2_May-2025
270
270
9.
9. Farmonov, S., & Nazirov, A. (2023). C# DASTURLASH TILIDA GRAY
KODI BILAN ISHLASH. В CENTRAL ASIAN JOURNAL OF EDUCATION
AND INNOVATION (Т. 2, Выпуск 12, сс. 71–74). Zenodo.
10.
10. Farmonov, S., & Toirov, S. (2023). NETDA DASTURLASHNING
ZAMONAVIY TEXNOLOGIYALARINI O'RGANISH.
Theoretical aspects in
the formation of pedagogical sciences
,
2
(22), 90-96
11.
11. Raxmonjonovich, F. S. (2023). Array ma’lumotlar tizimini talabalarga
o’qitishda Blockchain metodidan foydalanish.
Yangi O'zbekiston taraqqiyotida
tadqiqotlarni o'rni va rivojlanish omillari
,
2
(2), 541-547.
12.
12. Raxmonjonovich, F. S. (2023). Dasturlashda interfeyslardan foydalanishning
ahamiyati.
Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish
omillari
,
2
(2), 425-429.
13.
13. Raxmonjonovich, F. S. (2023). Dasturlashda obyektga yo’naltirilgan
dasturlashning ahamiyati.
Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va
rivojlanish omillari
,
2
(2), 434-438.
14.
14. Raxmonjonovich, F. S. (2023). Dasturlash tillarida fayllar bilan ishlash
mavzusini Blended Learning metodi yordamida o'qitish.
Yangi O'zbekiston
taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari
,
2
(2), 464-469.
15.
15. Raxmonjonovich, F. S. (2023). DASTURLASHDA ISTISNOLARNING
AHAMIYATI.
Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish
omillari
,
2
(2), 475-481.
16.
16. Raxmonjonovich, F. S. (2023). Dasturlashda abstraksiyaning o’rni.
Yangi
O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari
,
2
(2), 482-
486.
17.
17. Raxmonjonovich, F. S., & Ravshanbek o’g’li, A. A. (2023). Zamonaviy
dasturlash
tillarining
qiyosiy
tahlili.
Yangi
O'zbekiston
taraqqiyotida
tadqiqotlarni o'rni va rivojlanish omillari
,
2
(2), 430-433.
18.
18. Raxmonjonovich, F. S. (2023). C# dasturlash tilida fayl operatsiyalari
qo’llashning qulayliklari haqida.
Yangi O'zbekiston taraqqiyotida tadqiqotlarni
o'rni va rivojlanish omillari
,
2
(2), 439-446.
19.
19. Raxmonjonovich, F. S. (2023). C# tilida ArrayList bilan ishlashning
afzalliklari.
Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish
omillari
,
2
(2), 470-474.
20.
20. Farmonov Sherzodbek Raxmonjonovich, & Rustamova Humoraxon
Sultonbek qizi. (2024). C# DASTURLASH TILIDA TO’PLAMLAR BILAN
ISHLASH. Ta’lim Innovatsiyasi Va Integratsiyasi, 11(10), 210–214. Retrieved
from http://web-journal.ru/index.php/ilmiy/article/view/2480.
