Омӯзиши алгоритми Флойд–Уоршелл
Ба мо графи вазндори самтдор ё бесамт бо қулла дода шудааст. Мо бояд масофаи кӯтоҳтарин -ро байни ҳар як ҷуфти қуллаҳои ва пайдо кунем.
Граф метавонад канорҳо бо вазнҳои манфӣ дошта бошад, аммо он набояд ягон давраи бо вазни манфӣ дошта бошад.
Ин алгоритмро инчунин барои ошкор кардани давраҳои манфӣ истифода бурдан мумкин аст: агар баъд аз анҷоми алгоритм мо ба даст орем
барои ягон қуллаи , пас граф дорои давраи манфӣ мебошад.
Алгоритми Флойд–Уоршелл ҷавобро қадам ба қадам месозад.
Дар ҳар марҳила, мо қарор медиҳем, ки оё ҳангоми рафтан аз ба гузаштан аз як қуллаи дигар фоидаовар аст ё не.
Пеш аз марҳилаи , қимати d[x][y] дарозии роҳи кӯтоҳтаринро аз ба нигоҳ медорад, ки қуллаҳои дохилии он танҳо ба маҷмӯи
тааллуқ доранд.
Дар ин ҷо, қуллаҳои дохилӣ маънои ҳамаи қуллаҳои дар роҳро доранд, ба ҷуз аз оғоз ва анҷом.
Барои марҳилаи ибтидоӣ, мо мегузорем:
d[x][y] = w[x][y] агар аз ба каноре бо вазни вуҷуд дошта бошад;d[x][y] = inf агар каноре вуҷуд надошта бошад;d[x][x] = 0 барои ҳар як қуллаи .Акнун фарз мекунем, ки мо дар марҳилаи ҳастем ва мехоҳем матритсаро нав кунем.
Барои ҳар як ҷуфти қуллаҳо , ду имконият вуҷуд дорад:
Дар ҳолати дуюм, роҳро метавон ба ду қисм ҷудо кард:
Ҳар дуи ин қисмҳо танҳо қуллаҳои дохилиро аз маҷмӯи истифода мебаранд, бинобар ин дарозиҳои онҳо аллакай ҳисоб карда шудаанд.
Аз ин рӯ, гузариш чунин аст:
Пас дар ҳар марҳила, мо танҳо кӯшиш мекунем ҳар як ҷуфт -ро бо гузаштан аз қуллаи беҳтар кунем.
Пас аз ҳамаи марҳила, d[x][y] дарозии роҳи кӯтоҳтаринро аз ба $yдар бар мегирад, ёinf` агар чунин роҳ вуҷуд надошта бошад.
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]);
}
}
}