Mustaqil ishi Mavzu

Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti

Fan nomi: Ma’lumotlar tuzilmasi va algoritmlar

Mustaqil ishi

Mavzu: Graflarda eng qisqa yo’lni aniqlash algoritmlari



GURUH № 010-18(SAX)

BAJARDI : Xamroqulov Qodirjon

TEKSHIRDI: Muxsinov Sh.Sh.

TOSHKENT-2020

Variant № 20

Reja:

1. 
   Floyd Algoritmi eng qisqa yo'llarini topish algoritmlari haqida tushuncha .
   
2. 
   Deykstra algoritmi
   
3. 
   Eng qisqa yo'llarini topish algoritmlari misollar.
   
4. 
   Xulosa
   
5. 
   Foydalanilgan adabiyotlar ro’yhati.
   

Floyd Algoritmi

Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki u har qanday ikki ustun o'rtasida eng qisqa yo'llarni topadi.

Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng.

Floyd Algoritmi

Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz.

Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]

A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ;

k ga SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating.

Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i-yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi ( misol 45.2).

Misol 45.2. Floyd algoritmini namoyish qilish

// Floyd algoritm funktsiyasi tavsifi

void Floyd(int n, int **Graph, int **ShortestPath){

int i, j, k;

int Max_Sum = 0;

for ( i = 0 ; i < n ; i++ )

for ( j = 0 ; j < n ; j++ )

Max_Sum += ShortestPath[i][j];

for ( i = 0 ; i < n ; i++ )

for ( j = 0 ; j < n ; j++ )

if ( ShortestPath[i][j] == 0 && i != j )

ShortestPath[i][j] = Max_Sum;

for ( k = 0 ; k < n; k++ )

for ( i = 0 ; i < n; i++ )

for ( j = 0 ; j < n ; j++ )

if ((ShortestPath[i][k] + ShortestPath[k][j]) <

ShortestPath[i][j])

ShortestPath[i][j] = ShortestPath[i][k] +

ShortestPath[k][j];

}

Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya.

Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi.