Dots., t f. n. Boynazarov I. M. Ma’ruza rejasi Plan lecture

Floyd-Uorshell algorimti

• Floyd-Uorshell algorimti – bu vaznli yo’naltirnilgan graf (orgraf)da barcha tugunlar orasidagi eng qisqa masofalarni hisoblash uchun mo’ljallangan dinamik algoritm. Bu algoritm 1962 yil Robert Floyd va Stiven Uorshellar tomonidan ishlab chiqilgan.
• Yuqorida aytilganidek bu algoritm grafning barcha tugunlari orasidagi qisqa masofani (yo’lni) aniqlash uchun mo’ljallangan. Algoritmning maqsadi tugunlar orasidagi yo’llarni aniqlab olib, ular orasidagi eng kichigini tanlab olishdan iborat. Tugunlar orasidagi yo’l (yoyning vazni) “qo’shnilik matritsasi”ga joylashtriladi. Bizga ma’lumki bu matritsa NxN o’lchamli kvadrat matritsa bo’ladi (N - grafdagi tugunlar soni). Matritsaning i-satr va j-ustuni kesishgan yacheykasida grafning i va j tugunlar orasidagi masofa (yoy vazni) joylashadi (oldingi Deykstr algoritmi uchun ko’rib chiqilgan misollardagi matritsalarga qarang).

Floyd-Uorshell algoritmining tadbiqi

• Bu algoritmda qisqa yo’lni aniqlash uchta tsikl ichida bajariladi. Tashqi tsikl eng qisqa yo’lni topish uchun o’tadigan tugunlarni tanlab oladi, ichki ikkita tsikl esa, eng qisqa yo’l mavjud bo’lgan tugunlar juftliklarini tanlash uchun qo’llaniladi.
• Algoritmning tadbiqi uchun oddiy to’rtta tugundan iborat grafni qarab chiqamiz

berilgan grafning qo’shnilik matritsa quyidagicha bo’ladi:

• berilgan grafning qo’shnilik matritsa quyidagicha bo’ladi:

Bu matrtsiyaning asosiy diogonalida 0 qiymatlari joylashgan, chunki tugunning o’ziga-o’zi yoy mavjud emas yoki grafda xalqa (petlya) yo’q. Ikkinchi dioganalda 101 sonlari joylashtrilgan, bu joriy tugundan boshqa tugunga yoy (yo’l) yo’qligini bildiradi.

Algoritmning Dasturlash tilidagi kodi:

• //matrix – qo’shnilik matritsasi
• void originalFloydWarshall(int **matrix, int numberOfVert) {
• // k tugun orqali barcha tugunlar bo’ylab harakatlanib,
• // eng qisqa yo’lni qidiramiz
• for(int k = 0; k < numberOfVert; k++) {
• for(int i = 0; i < numberOfVert; i++) {
• for(int j = 0; j < numberOfVert; j++) {
• //yoyning yangi qiymati oldingi yoy va i <-> k + k <-> j yoylarning yig’indisi orasidagi minimal qiymatga teng (agar k yoy orqali tezroq o’tish mumkin bo’lsa)
• matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
• } } }
• return;
• }