De ce contează?
Ai o hartă de zboruri cu rute pe un singur sens. Te interesează o singură întrebare, repetată pentru fiecare pereche de orașe: „pot ajunge de la X la Y, fie și cu escale?" Nu te interesează cât durează sau câte escale — doar DA sau NU. Roy-Warshall completează exact acest tabel de accesibilitate, bifând fiecare pereche care e legată printr-un drum, oricât de întortocheat.
Intuiția
Pleci de la matricea de adiacență: a[i][j] = 1 dacă există arc direct
i -> j. Vrei să o transformi într-o matrice de accesibilitate: a[i][j] = 1
dacă există vreun drum i -> j, fie el și prin alte orașe.
Ideea e să permiți treptat fiecare oraș să fie escală. Întrebi: „dacă adaug
nodul k ca posibilă escală, apar perechi noi pe care le pot lega acum?" Dacă
ajung din i la k ȘI din k la j, atunci pot ajunge din i la j cu
escală în k. Repeți asta pentru fiecare k și tabelul se umple singur.
Regula de „sudare": a[i][j] devine 1 dacă a[i][k] ȘI a[k][j] sunt deja 1 —
două drumuri existente se lipesc cap la cap prin k. E exact schema lui
Roy-Floyd (aceeași buclă k exterioară), doar că pe adevărat/fals:
SAU/ȘI în loc de min/+.