“Floyd algoritmi” mavzusidagi

1.1.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.