De ce contează?
Imaginează-ți un tabel de distanțe rutiere, ca cel de pe spatele unei hărți: pe fiecare linie un oraș, pe fiecare coloană alt oraș, iar în celulă cea mai scurtă distanță dintre ele. La început completezi doar drumurile directe. Apoi te întrebi, oraș cu oraș: „dacă mi-aș permite să fac o oprire în Cluj, ar scurta vreun traseu?". Refaci tabelul. Apoi permiți și o oprire în Sibiu. Și tot așa, până ai voie să te oprești oriunde. Asta e Roy-Floyd.
Intuiția
Vrei distanța minimă între toate perechile de orașe, nu doar de la unul.
Ții un tabel d[i][j] cu cea mai scurtă distanță găsită până acum de la i la
j. Pornești de la muchiile directe și îl îmbunătățești treptat: pe rând, dai
„voie să treci prin nodul k" și verifici dacă un ocol prin k scurtează vreun
drum. După ce ai trecut în revistă toate nodurile intermediare posibile, tabelul
conține drumurile minime adevărate.
Semnificația lui k e invariantul întregului algoritm: după pasul k,
d[i][j] e drumul minim care folosește ca opriri intermediare DOAR noduri din
mulțimea . De aceea k e bucla exterioară: ca să extinzi
mulțimea de la la , ai nevoie ca d[i][k] și
d[k][j] să fie deja minime peste vechea mulțime — adică pasul k-1 să fie
complet terminat pentru toate perechile.
Atenție la sora acestei lecții: Roy-Warshall (închiderea tranzitivă) răspunde
doar la întrebarea „există drum de la i la j?" — un DA/NU, cu aceleași trei
bucle dar cu SAU/ȘI logic. Roy-Floyd, lecția de față, răspunde la „cât
costă cel mai scurt drum?" — cu min și + pe costuri.