Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish №3

gacha i uchun 1 dan |V|
gacha j uchun 1 dan |V|
gacha agar dist[ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ]
dist[ i ][ j ] ← dist[ i ][ k ] + dist[ k ][ j ]
oxiri agar

Misol.

Yuqoridagi algoritm quyidagi chapdagi grafikda bajariladi:

Yuqorida k = 0 deb belgilangan tashqi halqaning birinchi rekursiyasidan oldin faqat ma'lum bo'lgan yo'llar grafikdagi yagona qirralarga mos keladi. k = 1 da 1 cho‘qqidan o‘tuvchi yo‘llar topiladi: xususan, qirralari kamroq, lekin uzunroq (og‘irligi bo‘yicha) yo‘l [2,3] o‘rnini bosuvchi yo‘l [2,1,3] topiladi. ). k = 2 da {1,2} cho'qqilardan o'tuvchi yo'llar topiladi. Qizil va ko'k qutilar [4,2,1,3] yo'lning oldingi iteratsiyalarda uchragan ikkita ma'lum yo'llardan [4,2] va [2,1,3] qanday yig'ilganligini ko'rsatadi, kesishmada 2. [4,2,3] yo'li hisobga olinmaydi, chunki [2,1,3] 2 dan 3 gacha bo'lgan eng qisqa yo'ldir. k = 3 da, {1,2,3} uchlari orqali oʻtuvchi yoʻllar topiladi. Nihoyat, k = 4 da barcha eng qisqa yo'llar topiladi.
Yangilangan masofalar qalin harf bilan k ning har bir iteratsiyasidagi masofa matritsasi quyidagicha bo'ladi: Salbiy davrlar bilan xatti-harakatlar . Salbiy sikl - qirralari manfiy qiymatga ega bo'lgan tsikl. Har qanday cho'qqi juftligi orasida eng qisqa yo'l yo'q{\displaystyle i} ,{\displaystyle j} salbiy tsiklning bir qismini tashkil etuvchi, chunki yo'l uzunligi dan{\displaystyle i} uchun{\displaystyle j} o'zboshimchalik bilan kichik bo'lishi mumkin (salbiy). Raqamli ma'noli chiqish uchun Floyd-Uorshall algoritmi manfiy tsikllar yo'qligini taxmin qiladi. Shunga qaramay, agar salbiy tsikllar mavjud bo'lsa, ularni aniqlash uchun Floyd-Uorshall algoritmidan foydalanish mumkin. Intuitivlik quyidagicha:

• 
  Floyd-Uorshall algoritmi barcha cho'qqilar juftligi orasidagi yo'l uzunligini iterativ ravishda qayta ko'rib chiqadi.{\displaystyle (i,j)} , shu jumladan qaerda{\displaystyle i=j} ;
  
• 
  Dastlab, yo'lning uzunligi{\displaystyle (i,i)} nolga teng;
  
• 
  Yo'l{\displaystyle [i,k,\ldots,i]} faqat uning uzunligi noldan kichik bo'lsa, ya'ni manfiy siklni bildirsa, uni yaxshilash mumkin;
  
• 
  Shunday qilib, algoritmdan keyin{\displaystyle (i,i)} dan salbiy uzunlikdagi yo'l mavjud bo'lsa, salbiy bo'ladi{\displaystyle i} Orqaga{\displaystyle i} .
  

Demak, Floyd-Uorshall algoritmi yordamida manfiy sikllarni aniqlash uchun yo'l matritsasining diagonalini tekshirish mumkin va manfiy sonning mavjudligi grafikda kamida bitta manfiy sikl borligini ko'rsatadi. ^[9] Algoritmni bajarish jarayonida manfiy sikl mavjud boʻlsa, eksponensial darajada katta sonlar paydo boʻlishi mumkin.{\displaystyle \Omega (\cdot 6^{n-1}w_{max})} , qayerda{\ displaystyle w_ {max}} - grafikdagi manfiy chekkaning eng katta mutlaq qiymati. To'lib ketish/to'lib ketish muammolarini oldini olish uchun algoritmning ichki for tsikli ichidagi yo'l matritsasining diagonalida manfiy raqamlar mavjudligini tekshirish kerak. ^[10] Shubhasiz, yoʻnaltirilmagan grafikda manfiy chekka oʻzining tushuvchi uchlarini oʻz ichiga olgan manfiy sikl (yaʼni, yopiq yurish) hosil qiladi. Yuqoridagi misol grafikning barcha qirralarini yo'naltirilmagan deb hisoblasak, masalan, 4 – 2 – 4 cho'qqilar qatori og'irlik yig'indisi -2 bo'lgan sikldir.