Floyd–Warshall algoritmini o‘rganing
Bizga ta cho‘qqiga ega yo‘naltirilgan yoki yo‘naltirilmagan og‘irlikli graf berilgan. Biz har bir va cho‘qqilar jufti orasidagi eng qisqa masofa ni topishimiz kerak.
Grafda manfiy og‘irlikli qirralar bo‘lishi mumkin, ammo unda manfiy og‘irlikli sikl bo‘lishi mumkin emas.
Ushbu algoritm manfiy sikllarni aniqlash uchun ham ishlatilishi mumkin: agar algoritm tugagandan so‘ng
biror cho‘qqi uchun bajarilsa, u holda grafda manfiy sikl mavjud.
Floyd–Warshall algoritmi javobni bosqichma-bosqich quradi.
Har bir bosqichda, dan ga borishda yana bitta cho‘qqi orqali o‘tish foydali yoki yo‘qligini hal qilamiz.
-bosqichdan oldin, d[x][y] qiymati dan ga eng qisqa yo‘l uzunligini saqlaydi, uning ichki cho‘qqilari faqat quyidagi to‘plamga tegishli bo‘ladi:
Bu yerda ichki cho‘qqilar deganda yo‘ldagi boshlanish va tugashdan tashqari barcha cho‘qqilar nazarda tutiladi.
Boshlang‘ich bosqich uchun, quyidagicha o‘rnatamiz:
d[x][y] = w[x][y];d[x][y] = inf;d[x][x] = 0.Endi -bosqichda ekanligimizni va matritsani yangilamoqchi ekanligimizni faraz qilaylik.
Har bir cho‘qqilar jufti uchun ikki imkoniyat bor:
Ikkinchi holatda, yo‘lni ikki qismga ajratish mumkin:
Bu qismlarning har ikkalasi ham faqat to‘plamidan ichki cho‘qqilardan foydalanadi, shuning uchun ularning uzunliklari allaqachon hisoblab bo‘lingan.
Shuning uchun, o‘tish quyidagicha:
Demak, har bir bosqichda biz shunchaki cho‘qqi orqali o‘tib, har bir juftini yaxshilashga urinib ko‘ramiz.
Barcha bosqichdan so‘ng, d[x][y] dan ga eng qisqa yo‘l uzunligini, yoki bunday yo‘l mavjud bo‘lmasa inf ni o‘z ichiga oladi.
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}