Mavzu: Floyd-Uorshell algoritmi

Salbiy tsikllarning holati

Agar grafikda salbiy og'irlik tsikllari bo'lsa, unda Floyd-Warshall algoritmi rasmiy ravishda bunday grafikka tegishli emas. Ammo, aslida algoritm barcha juftliklar uchun to'g'ri ishlaydi, ularning yo'llari hech qachon manfiy tsikldan o'tmaydi, qolganlari uchun biz ba'zi raqamlarni olamiz, ehtimol juda salbiy. Algoritm-ga mos keladigan bunday juftliklar uchun ma'lum bir qiymat olishni o'rgatish mumkin.

Aytgancha, bunday grafikni ishlab chiqqandan so'ng, qisqa yo'llar matritsasining diagonalida manfiy sonlar paydo bo'ladi - bu tsiklning uchidan unga eng qisqa masofa noldan kam bo'ladi, bu tsiklning o'tishiga to'g'ri keladi. Algoritmni grafikda salbiy tsikllarning mavjudligini aniqlash uchun ishlatish mumkin.

Yo'lni qayta qurish

Masofa matritsasi bizga har qanday vertikal juftlik uchun eng qisqa (eng arzon) masofani ko'rsatadi, ammo siz qanday qilib yo'lni bilasiz? D hisoblash juda oddiy, ^k _ij, bir ham hisoblash π kerak ^k _ij . π ^k _ij bu holatda uch v salafiy deb _j V yo'lda _i ruxsat oraliq uchlari {1..k} majmui bilan.

-natija