FLOYD-WARSHALL ALGORITMI VA UNING O'YINLAR VA SUN'IY INTELLEKTDAGI QO'LLANILISHI

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

4

FLOYD-WARSHALL ALGORITMI VA UNING O'YINLAR VA SUN'IY

INTELLEKTDAGI QO'LLANILISHI

Farmonov Sherzodbek Raxmonjonovich

Fargʻona davlat universiteti amaliy matematika va informatika

kafedrasi katta o’qituvchisi

farmonovsh@gmail.com

Abdullayev Abrorbek Dilmurod oʻgʻli

Fargʻona davlat universiteti 2-kurs talabasi

aadabdullayev1@gmail.com

https://doi.org/10.5281/zenodo.14287809

Annotatsiya.

Bu algoritm o‘yinlar va sun'iy intellekt (AI) sohalarida bir qancha

masalalarni hal qilishda keng qo‘llaniladi. O‘yinda harakatlarni rejalashtirish, resurslarni
taqsimlash, strategik qarorlar qabul qilish, tarmoq aloqalarini optimallashtirish kabi vazifalar
uchun Floyd-Warshall algoritmi samarali vosita hisoblanadi.O'yinlarda, masalan, strategik
o‘yinlarda xarakterlar yoki agentlar o‘rtasidagi eng qisqa yo‘llarni aniqlashda, labirint
o‘yinlarida yoki transport tizimlarida bu algoritm harakatlarni optimallashtirish uchun
ishlatiladi. O‘yinlar ichida, masalan, xarakterning bir nuqtadan boshqasiga borishida, Floyd-
Warshall algoritmi xaritada mavjud barcha nuqtalar o‘rtasidagi eng qisqa yo‘llarni topishga
yordam beradi.

Kalit soʻzlar.

Floyd-Warshall algoritmi, eng qisqa yo‘l, graf nazariyasi, o'yinlar, sun'iy

intellekt (AI), optimal qarorlar qabul qilish, resurslarni taqsimlash, harakatlarni rejalashtirish,
labirint o‘yinlari, transport tizimlari, strategik qarorlar, tarmoq optimizatsiyasi,
robototexnika, blockchain.

Abstract.

In games and artificial intelligence (AI), the Floyd-Warshall algorithm is

widely applied for solving problems like path planning, resource allocation, strategic decision-
making, and network optimization. In games, especially in maze games or strategy games, it
can be used to determine the shortest paths between characters or agents. Similarly, in AI, it
aids in optimal decision-making and helps robots or agents make efficient movement
decisions based on the shortest path calculations.

The algorithm is particularly useful in robotics, where it can be used to plan the shortest

path for robots to move between points in an environment. Additionally, it plays a role in
optimizing transportation systems, network routing, and blockchain systems, where it helps
in reducing latency and improving the overall performance of data flow.

Keywords.

Floyd-Warshall algorithm, shortest path, graph theory, games, artificial

intelligence (AI), optimal decision making, resource allocation, path planning, maze games,
transportation systems, strategic decisions, network optimization, robotics, blockchain.

Аннотация

. В играх и искусственном интеллекте (ИИ) алгоритм Флойда-

Уоршалла широко используется для решения таких задач, как планирование пути,
распределение ресурсов, стратегическое принятие решений и оптимизация сетей. В
играх, особенно в лабиринтных играх или стратегиях, его можно использовать для
нахождения кратчайших путей между персонажами или агентами. Также в ИИ
алгоритм помогает в оптимальном принятии решений и помогает роботам или

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

5

агентам эффективно планировать движение, основываясь на вычислениях
кратчайшего пути.

Алгоритм особенно полезен в робототехнике, где его можно использовать для

планирования кратчайшего пути для роботов между точками в окружающей среде.
Кроме того, он играет важную роль в оптимизации транспортных систем,
маршрутизации сетей и блокчейн-систем, где он помогает сократить задержки и
улучшить общую производительность передачи данных.

Kлючевые слова.

Алгоритм Флойда-Уоршалла, кратчайший путь, теория графов,

игры, искусственный интеллект (ИИ), оптимальное принятие решений, распределение
ресурсов, планирование пути, лабиринтные игры, транспортные системы,
стратегические решения, оптимизация сетей, робототехника, блокчейн.

Floyd-Warshall algoritmi — bu graf nazariyasida ishlatiladigan eng qisqa yo‘lni

hisoblash algoritmlaridan biridir. Bu algoritm har bir juft nuqta orasidagi eng qisqa yo‘lni
topish uchun mo‘ljallangan bo‘lib, unda barcha nuqtalar o‘rtasidagi masofalar (yoki yo‘llar)
tahlil qilinadi. Algoritmning asosiy afzalligi shundaki, u hamma nuqtalar orasidagi eng qisqa
yo‘lni bir vaqtning o‘zida topishga imkon beradi, shuning uchun u yirik graf tizimlari va
kompleks bog‘lanishlar uchun juda qulay.

Floyd-Warshall algoritmi, ayniqsa, barcha juft nuqtalar orasidagi eng qisqa yo‘lni topish

zarur bo‘lganda samarali bo‘ladi. O‘yinlar va sun'iy intellekt (AI) sohalarida, bu algoritm
ko‘pincha harakatlarni rejalashtirish, optimallashtirish va strategik qarorlar qabul qilish
jarayonlarida qo‘llaniladi.

Floyd-Warshall algoritmi va uning asosiy prinsipi

Floyd-Warshall algoritmi asosan quyidagi prinsipga asoslanadi:

1.

Graf tuzilishi

: Grafdagi har bir nuqta va nuqtalar o‘rtasidagi masofalar (qirralar)

ko‘rsatiladi. Bu matritsa shaklida ifodalanadi.
2.

Dinamika

: Har bir nuqtaning boshqa nuqtalarga eng qisqa yo‘lini hisoblashda, algoritm

oraliq nuqtalar

ni kiritadi. Ya'ni, har bir juft nuqta orasidagi eng qisqa yo‘lni topishda oraliq

nuqtalar orqali harakat qilish imkoniyati hisobga olinadi.
3.

Yakuniy natija

: Algoritm barcha juft nuqtalar orasidagi eng qisqa yo‘lni hisoblaydi va

natijada matritsa hosil bo‘ladi, unda

D[i][j]

qiymati i nuqtadan j nuqtaga eng qisqa yo‘lni

ko‘rsatadi.
Floyd-Warshall algoritmining rasmiy formulasi quyidagicha:
D[i][j]=min

⁡

(D[i][j],D[i][k]+D[k][j])D[i][j]

=

\min(D[i][j],

D[i][k]

+

D[k][j])D[i][j]=min(D[i][j],D[i][k]+D[k][j])
Bu yerda:



D[i][j]D[i][j]D[i][j] — iii-nuqtadan jjj-nuqtaga eng qisqa yo‘l,



D[i][k]D[i][k]D[i][k] — iii-nuqtadan kkk-nuqtaga eng qisqa yo‘l,



D[k][j]D[k][j]D[k][j] — kkk-nuqtadan jjj-nuqtaga eng qisqa yo‘l.

O'yinlar va Sun'iy Intellektdagi Qo'llanilishi
1. O'yinlar va o'yin dizayni

Floyd-Warshall algoritmi

o‘yinlarda

harakatlarni rejalashtirish va xaritalardagi eng qisqa

yo‘llarni aniqlash uchun ishlatiladi. Masalan, o‘yinlar ichida xarakterlar (yoki o‘yin agentlari)

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

6

o‘rtasidagi eng qisqa yo‘lni aniqlash, yoki xaritada bir nuqtadan boshqasiga eng samarali
yo‘lni tanlashda foydalanish mumkin.

Misollar:



Labirintlar va sarguzasht o‘yinlari

: Labirint o‘yinlarida, o‘yinchi yoki robot labirintda

eng qisqa yo‘lni topish uchun

Floyd-Warshall algoritmi

ni ishlatishi mumkin. Bu algoritm

labirintning har bir bo‘sh xujayrasini nuqta sifatida ko‘rib chiqib, barcha nuqtalar orasidagi
eng qisqa yo‘lni hisoblaydi.



Transport tizimlari va resurslar oqimi

: Agar o‘yinda xaritalar bo‘lsa, unda xarita

bo‘yicha turli joylar orasida eng qisqa yo‘lni tanlash va resurslar yoki birliklarni optimal
yo‘nalishda jo‘natish zarur. Misol uchun, strategik o‘yinlarda bazalardan turli nuqtalarga yoki
boshqa hududlarga tezkor resurslarni yetkazib berish uchun Floyd-Warshall algoritmi
ishlatiladi.



RPG o‘yinlarida qarorlar qabul qilish

: Rol o‘ynash o‘yinlarida (RPG), xarakterlar

orasida aloqalarni o‘rnatish, ya'ni "do‘stlik tarmog‘i" o‘rnatish uchun Floyd-Warshall algoritmi
qo‘llaniladi. Bu, masalan, o‘yinchi boshqa o‘yinchilarga yoki NPC (non-player characters) bilan
aloqada bo‘lishda minimal vaqtni hisoblashda ishlatilishi mumkin.

2. Sun'iy Intellekt (AI)

Sun'iy intellektda, Floyd-Warshall algoritmi bir nechta sohalarda qo‘llaniladi, xususan yo‘l
rejalashtirish, muammolarni optimallashtirish va qarorlar qabul qilish jarayonlarida.

Misollar:



Robototexnika

: Robotlar uchun eng qisqa yo‘lni topish, ayniqsa murakkab muhitda,

Floyd-Warshall algoritmi

orqali amalga oshirilishi mumkin. Masalan, bir robotning boshqa

bir nuqtadan boshqa nuqtaga eng qisqa yo‘lni tanlashi, o‘yinlarda yoki haqiqiy dunyo
sharoitida o‘zgarishi mumkin bo‘lgan holatlarni hisobga olib, optimal qarorlarni qabul qilish
zarur.



Strategik qarorlar qabul qilish

: AI agentlari murakkab vazifalarni bajarishda eng qisqa

yoki eng tejamkor yo‘lni tanlashi kerak bo‘lgan holatlar uchun (masalan, resurslarni sarflash
yoki strategik maqsadlarni amalga oshirish) Floyd-Warshall algoritmi ishlatiladi.
O‘zgaruvchan muhitda optimizatsiya qilishda yordam beradi.

Masala:

Eng qisqa yo‘lni topish

Berilgan 2D matritsa (labirint) yordamida boshlang‘ich nuqtadan tugash nuqtasiga bo‘lgan
eng qisqa yo‘lni toping. Yo‘llar bo‘sh xujayralar (0) bilan belgilangan, devorlar esa 1 bilan
belgilangan. Biz boshlanish nuqtasi S va tugash nuqtasi T nuqtalarini belgilaymiz.

Masala tafsifi:

1.

Labirint

2D matritsa sifatida beriladi. Har bir xujayra:



0

- bo‘sh xujayra (harakat qilish mumkin),



1

- devor (harakat qilish mumkin emas).

2.

Boshlanish

nuqtasi S (0, 0) va

tugash

nuqtasi T (oxirgi xujayra) bo‘ladi.

3.

Harakat faqat

pastga, yuqoriga, o‘ngga va chapga

bo‘lishi mumkin.

Masala

4.

Labirintdan boshlash nuqtasidan tugash nuqtasigacha eng qisqa yo‘lni toping.

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

7

5.

Agar eng qisqa yo‘l mavjud bo‘lmasa, "Yo‘l topilmadi" deb xabar bering.

using System;

class Labirint
{
// Labirintdagi harakat qilish mumkin bo'lgan nuqtalar
static int[] rowDirections = { -1, 1, 0, 0 }; // Yuqoriga, Pastga, Chapga, O'ngga
static int[] colDirections = { 0, 0, -1, 1 };

// Labirintni tekshirish funksiyasi (BFS yordamida)
static bool IsValidMove(int[,] labirint, bool[,] visited, int x, int y, int n, int m)
{
return x >= 0 && x < n && y >= 0 && y < m && labirint[x, y] == 0 && !visited[x, y];
}

// Eng qisqa yo'lni topish uchun BFS algoritmi
static void FindShortestPath(int[,] labirint, int n, int m)
{
// Boshlang'ich nuqta (0, 0) va tugash nuqtasi (n-1, m-1)
int startX = 0, startY = 0;
int endX = n - 1, endY = m - 1;

// Qo'llaniladigan navbat va masofa
Queue<(int, int, int)> queue = new Queue<(int, int, int)>(); // (x, y, masofa)
bool[,] visited = new bool[n, m]; // Qaysi nuqtalar tekshirilgan

// Boshlang'ich nuqtaga qo'shish
queue.Enqueue((startX, startY, 0)); // Boshlang'ich nuqtani va masofani 0 deb qo'yamiz
visited[startX, startY] = true;

while (queue.Count > 0)
{
var (x, y, distance) = queue.Dequeue();

// Agar tugash nuqtasiga yetib borgan bo'lsak, masofani chiqaramiz
if (x == endX && y == endY)
{
Console.WriteLine("Eng qisqa yo'l topildi, masofa: " + distance);
return;
}

// Harakat qilishi mumkin bo'lgan nuqtalarni tekshiramiz
for (int i = 0; i < 4; i++)

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

8

{
int newX = x + rowDirections[i];
int newY = y + colDirections[i];

if (IsValidMove(labirint, visited, newX, newY, n, m))
{
visited[newX, newY] = true;
queue.Enqueue((newX, newY, distance + 1)); // Yangi nuqtaga masofani 1 ta
qo‘shamiz
}
}
}

// Agar tugash nuqtasiga yetib bormagan bo‘lsak
Console.WriteLine("Yo'l topilmadi.");
}

static void Main()
{
// Labirint (2D matritsa)
int[,] labirint = new int[4, 5]
{
{ 0, 0, 1, 1, 0 },
{ 1, 0, 1, 0, 0 },
{ 1, 0, 0, 0, 1 },
{ 0, 1, 1, 0, 0 }
};

int n = labirint.GetLength(0); // Labirintning qatorlari soni
int m = labirint.GetLength(1); // Labirintning ustunlari soni

// Eng qisqa yo'lni topish
FindShortestPath(labirint, n, m);
}
}

Dasturning ishlash jarayoni:

1.

Labirintni belgilash

: Labirint 2D matritsa ko‘rinishida beriladi, bunda 0 — bo‘sh

xujayra (harakat qilish mumkin), 1 esa devor (harakat qilish mumkin emas).
2.

BFS

algoritmi yordamida eng qisqa yo‘lni topish:

o

Biz BFS algoritmini ishlatamiz, chunki BFS birinchi marta tugash nuqtasiga yetib

borganida, bu eng qisqa yo‘l bo‘ladi.

o

Queue

(navbat) yordamida har bir nuqtani tekshirib chiqamiz va har bir nuqtadan

keyingi nuqtaga qanday borish mumkinligini ko‘rib chiqamiz.

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

9

3.

Natija

: Agar biz tugash nuqtasiga yetib borsak, masofani chiqaramiz, aks holda "Yo‘l

topilmadi" deb chiqamiz.

Floyd-Warshall algoritmi — bu ko‘p murakkab tizimlarda va tarmoqlarda ishlatiladigan

kuchli vositadir. O‘yinlar va sun'iy intellektda uning qo‘llanilishi juda kengdir. U harakatlarni
rejalashtirish, yo‘lni optimallashtirish, qarorlar qabul qilish va tarmoq aloqalarini tahlil qilish
kabi ko‘plab vazifalarni samarali tarzda bajarishga yordam beradi. Bu algoritmning eng katta
afzalligi shundaki, u barcha juft nuqtalar orasidagi eng qisqa yo‘lni topishga imkon beradi, bu
esa ayniqsa murakkab tizimlar va yirik o‘yinlarda muhim rol o‘ynaydi.

References:

1.

Marcin Jamro. C# Data Structures and Algorithms. Second Edition. Published by Packt

Publishing Ltd., in Birmingham, UK. 2024. – 349 p.
2.

Дж.Эриксон. Алгоритмы.: – М.: " ДМК Пресс ", 2023. – 528 с.

3.

Hemant Jain. Data Structures & Algorithms using Kotlin. Second Edition. in India. 2022. –

572 p.
4.

Н. А. Тюкачев, В. Г. Хлебостроев. C#. Алгоритмы и структуры данных: учебное

пособие для СПО. – СПб.: Лань, 2021. – 232 с.
5.

Mykel J. Kochenderfer. Tim A. Wheeler. Algorithms for Optimization. Published by The

MIT Press., in London, England. 2019. – 500 p.
6.

Рафгарден Тим. Совершенный алгоритм. Графовые алгоритмы и структуры

данных. – СПб.: Питер, 2019. - 256 с.
7.

Ахо Альфред В., Ульман Джеффри Д., Хопкрофт Джон Э. Структуры данных и

алгоритмы. – М.: Вильямс, 2018. – 400 с.
8.

Дж.Хайнеман, Г.Поллис, С.Стэнли. Алгоритмы. Справочник с примерами на С, C++,

Java и Python, 2-е изд.: Пер. с англ. — СпБ.: ООО "Альфа-книга", 2017. — 432 с.
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.

Farmonov, S., & Toirov, S. (2023). NETDA DASTURLASHNING ZAMONAVIY

TEXNOLOGIYALARINI O'RGANISH.

Theoretical aspects in the formation of pedagogical

sciences

,

2

(22), 90-96

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.

Raxmonjonovich, F. S. (2023). Dasturlashda interfeyslardan foydalanishning

ahamiyati.

Yangi O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari

,

2

(2), 425-

429.

Eng qisqa yo'l topildi, masofa: 8

ILM-FAN VA INNOVATSIYA

ILMIY-AMALIY KONFERENSIYASI

in-academy.uz/index.php/si

10

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.

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.

Raxmonjonovich, F. S. (2023). DASTURLASHDA ISTISNOLARNING AHAMIYATI.

Yangi

O'zbekiston taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari

,

2

(2), 475-481.

16.

Raxmonjonovich, F. S. (2023). Dasturlashda abstraksiyaning o’rni.

Yangi O'zbekiston

taraqqiyotida tadqiqotlarni o'rni va rivojlanish omillari

,

2

(2), 482-486.