Floyd algoritmi grafikdagi istalgan ikkita cho'qqi orasidagi eng qisqa masofani topishga imkon beradi, chekka og'irliklari esa ijobiy yoki salbiy bo'lishi mumkin. Ushbu algoritm dinamik dasturlash g'oyasidan foydalanadi

Floyd algoritmi grafikdagi istalgan ikkita cho'qqi orasidagi eng qisqa masofani topishga imkon beradi, chekka og'irliklari esa ijobiy yoki salbiy bo'lishi mumkin. Ushbu algoritm dinamik dasturlash g'oyasidan foydalanadi. Grafikda 0 dan n−1 gacha raqamlangan n ta burchak bor deb faraz qilamiz. Grafik qo'shnilik matritsasi bilan berilgan, chekkaning og'irligi (i−j) w[i][j] da saqlanadi. Qirra (i - j) bo'lmasa, w[i][j]=+∞(INF) qiymati bo'lmasa, w[i][i]=0 (ko'chadan yo'q) deb ham faraz qilamiz.
a[k][i][j] qiymati i cho‘qqidan j cho‘qqigacha bo‘lgan eng qisqa yo‘l uzunligiga teng bo‘lsin va yo‘l oraliq cho‘qqilarga faqat k dan kichik sonlar bilan kirishi mumkin (boshi va oxirini hisobga olmaganda). yo'l). Ya'ni, a[0][i][j] - i dan j gacha bo'lgan eng qisqa yo'lning uzunligi, unda oraliq uchlari umuman yo'q, ya'ni u faqat bitta chetidan (i−j) iborat, shuning uchun a[0][i] [j]=w[i][j] (dastlabki chekka og'irligi (i-j)). a[1][i][j]=w[i][j] qiymati 0 raqami boʻlgan oraliq choʻqqidan oʻtishi mumkin boʻlgan eng qisqa yoʻl uzunligiga, ogʻirligi a[2][i boʻlgan yoʻlga teng. ][j] 0 va 1 raqamlari boʻlgan oraliq choʻqqilardan oʻtishi mumkin va hokazo. Ogʻirligi a[n][i][j] boʻlgan yoʻl har qanday oraliq uchlardan oʻtishi mumkin, shuning uchun a[n][i][ qiymati j] j dagi i dan eng qisqa yo‘l uzunligiga teng.
Floyd algoritmi a[0][i][j], a[1][i][j], A[2][i][j], …, a[n][i][j] ni ketma-ket baholaydi. k parametrining qiymatini oshirish. Dastlabki qiymat, yuqorida aytib o'tilganidek, a[0][i][j]=w[i][j]. Endi a[k-1][i][j] qiymatlari ma'lum deb faraz qilib, a[k][i][j] hisoblaymiz. Sonlari k dan kichik boʻlgan choʻqqilardan oʻtuvchi i choʻqqidan j choʻqqigacha boʻlgan eng qisqa yoʻl k−1 sonli uchni oʻz ichiga olishi yoki boʻlmasligi mumkin. Agar unda k−1 sonli cho‘qqi bo‘lmasa, bu yo‘lning og‘irligi a[k-1][i][j] bilan bir xil bo‘ladi. Agar u k−1 cho‘qqisini o‘z ichiga olsa, bu yo‘l ikki qismga bo‘linadi: i cho‘qqidan k−1 cho‘qqigacha va k−1 cho‘qqidan jgacha. Shuning uchun, ko'rib chiqilgan ikkita variantdan eng past narx variantini tanlash kerak: A[k][i][j] = min(A[k - 1][i][j], A[k - 1][i][k - 1] + A[k - 1][k - 1][j]);
U
shbu algoritmdagi tashqi halqa barcha cho'qqilarni ketma-ketlikda takrorlaydi, so'ngra tanlangan cho'qqidan o'tishga ruxsat berib, i dan j gacha bo'lgan yo'llarni yaxshilashga harakat qiladi. Keling, A massivning “uch o‘lchovliligi”dan xalos bo‘lish orqali ushbu algoritmni soddalashtiramiz: biz faqat i dan j gacha bo‘lgan eng qisqa yo‘lning qiymatini A[i][j] ga saqlaymiz va yo‘l yaxshilanganda, biz yo'lning yangi uzunligini ham A[i][j] da yozadi. Shuningdek, k o‘zgaruvchisi ustidagi sikl ta’rifini o‘zgartirib, k-1 qiymatini k bilan almashtiramiz.

Shubhasiz, bunday algoritmning murakkabligi O(n^3 ). E'tibor bering, agar salbiy og'irlikning qirralari bo'lsa, A[i][j] qiymatlari kamayishi mumkin. Shu sababli, A[i][j] qiymati INF ga teng bo'lganligi va keyin salbiy og'irlikdagi qirralarning mavjudligi sababli pasayganligi ma'lum bo'lishi mumkin. Natijada, A[i][j] qiymati INF dan kichik bo'lib chiqdi (masalan, INF uzunlikdagi yo'l va manfiy og'irlik yo'lining kombinatsiyasi tufayli), lekin hali ham o'rtasida yo'l yo'q. i va j uchlari. Shuning uchun, A[i][k] va A[k][j] ning INF ga teng emasligini qo'shimcha tekshirish kerak yoki INF dan bir oz pastroq qiymatlar ham yo'lning yo'qligi sifatida ko'rib chiqilishi kerak.

Floyd algoritmi manfiy og'irlik sikli mavjud bo'lganda to'g'ri ishlamaydi, lekin agar i dan j gacha bo'lgan yo'lda manfiy og'irlik sikli bo'lmasa, u holda bu yo'lning og'irligi algoritm orqali to'g'ri topiladi. Bundan tashqari, ushbu algoritmdan foydalanib, siz manfiy og'irlik tsiklining mavjudligini aniqlashingiz mumkin: agar i tepasi manfiy og'irlik siklida joylashgan bo'lsa, u holda algoritm tugagandan so'ng A[i][i] qiymati manfiy bo'ladi.
Javobni tiklash Javobni qayta tiklash uchun o'tmishdoshlarning ikki o'lchovli massivi kerak. Faraz qilamizki, Prev[i][j] i cho‘qqidan eng qisqa yo‘lda j cho‘qqisining oldingi qismi bo‘lgan cho‘qqi sonini o‘z ichiga oladi. Keyin A[i][j] qiymatini yangilaganingizda, avvalgisini ham yangilashingiz kerak. Ya'ni, agar (i−j) yo'l k tugunidan o'tuvchi yo'lga yangilangan bo'lsa, endi i dan yo'ldagi j tugunning oldingisi k dan yo'lda o'zidan oldingi tugunga aylanadi, ya'ni siz. Oldingi[i][ j]=Oldingi[k][j] ni belgilash kerak. Keling, oldingilarni saqlaydigan algoritm yozaylik, shuningdek, yo'l mavjudligini tekshirishni qo'shamiz.

Dinamika bo'yicha barcha muammolarda bo'lgani kabi, i dan j gacha bo'lgan yo'lni tiklash standartdir