Warshall algoritm , numit uneori algoritmul Roy-Warshall, este un algoritm care acționează pe un grafic . Permite construirea închiderii tranzitive a unui grafic direcționat sau neorientat, adică să construiască un al doilea grafic pe același set de vârfuri, cu un arc de la un vârf u la un vârf v , dacă și numai dacă există o cale în original grafic de la u la v . Prin urmare, acest algoritm oferă informații despre componentele conectate sau puternic conectate ale unui grafic.
Algoritmul își datorează numele lui Stephen Warshall care l-a publicat în 1962 și a fost descris și de Bernard Roy în 1959. Robert W. Floyd a publicat în Comunicările ACM algoritmul cu patru linii (Algoritmul 96) împreună cu algoritmul său de calcul cele mai scurte căi (Algoritmul 97) cunoscut sub numele de algoritmul Floyd-Warshall .
Din matricea de adiacență C a unui grafic G , algoritmul calculează matricea de adiacență C * a închiderii tranzitive a graficului. Vârfurile graficului sunt numerotate de la 1 la n .
Algoritmul calculează o succesiune de matrici C k de matrici, pentru k = 0, ..., n . Matricea C 0 este matricea C din matricea C n este matricea C * căutată. Matricile C k verifică proprietatea că C k [ i, j ] = 1 dacă există o cale de la i la j care trece doar prin vârfuri mai mici sau egale cu k și 0 în caz contrar.
Această proprietate caracteristică este bine verificată pentru k = 0 și pentru k = n . Pentru a construi matricea C k , observăm că există o cale de la i la j care trece doar prin vârfuri mai mici sau egale cu k dacă și numai dacă există o cale de la i la j care trece doar prin vârfuri inferioare sau egală cu k- 1 sau dacă există o cale de la i la k care trece prin vârfuri mai mici sau egale cu k-1 și o cale de la k la j care trece prin vârfuri mai mici sau egale cu k-1 . Ce se poate formula prin:
.Acest principiu este utilizat și în algoritmul Floyd-Warshall .
Putem scrie algoritmul în pseudo-cod după cum urmează (aici C este matricea asociată a graficului):
Roy-Warshall (C) C0 = C pour k de 1 à n pour i de 1 à n pour j de 1 à n Ck[i,j] = Ck-1[i,j] or (Ck-1[i,k] and Ck-1[k,j]) retourner CnSe poate optimiza algoritmul efectuând calculul în loc într-o singură matrice C. Următorul pseudo-cod efectuează acest calcul:
Roy-Warshall (C) pour k de 1 à n pour i de 1 à n pour j de 1 à n C[i,j] = C[i,j] or (C[i,k] and C[k,j]) retourner CExpresia booleană este rescrisă cu condiționali după cum urmează:
Roy-Warshall (C) pour k de 1 à n pour i de 1 à n si C[i,k] alors pour j de 1 à n si C[k,j] alors C[i,j] = true retourner CAceasta este exact formularea algoritmului publicat în comunicările ACM.
Exemplu de funcție programată în C care, pentru matricea de adiacență binară C a graficului G dat, calculează matricea de adiacență A a lui G * .
typedef _Bool MatAdj[n][n]; // où n est le nombre de sommets de G void Warshall(MatAdj C, // la matrice d'adjacence de G MatAdj A) // la matrice d'adjacence de G* { int i, j, k; for(i = 0; i < n; i++) for(j = 0; j < n; j++) A[i][j] = C[i][j]; for(k = 0; k < n; k++) for(i = 0; i < n; i++) for(j = 0; j < n; j++) A[i][j] = A[i][j] || (A[i][k] && A[k][j]); }Construcția închiderii tranzitive de către algoritmul Warshall are o complexitate în . Cu toate acestea, poate fi interesant să construim o dată pentru totdeauna închiderea tranzitivă a unui grafic; astfel, se poate ști printr-o simplă inspecție dacă vârfurile i și j aparțin aceleiași componente conectate într-un timp constant (rezervat sistemelor statice).