Warshall-algoritme

Den Warshall algoritme , også kaldet Roy-Warshall algoritme, er en algoritme, der virker på en graf . Det giver mulighed for at opbygge den transitive lukning af en rettet eller ikke-rettet graf, dvs. bygge en anden graf på det samme sæt hjørner med en bue fra et hjørne u til et hjørne v , hvis og kun hvis der er en sti i originalen graf fra u til v . Denne algoritme giver derfor information om de tilsluttede eller stærkt forbundne komponenter i en graf.

Historisk

Algoritmen skylder sit navn til Stephen Warshall, der offentliggjorde den i 1962, og den blev også beskrevet af Bernard Roy i 1959. Robert W. Floyd offentliggjorde i Communications of the ACM firelinjealgoritmen (Algoritme 96) sammen med dens algoritme til beregning korteste stier (algoritme 97) kendt som Floyd-Warshall-algoritmen .

Princip

Fra adjacency matrix C i en graf G beregner algoritmen adjacency matrix C * for den transitive lukning af grafen. Grafens hjørner er nummereret fra 1 til n .

Algoritmen beregner en sekvens af matricer C k af matricer, for k = 0, ..., n . Matrixen C 0 er matricen C fra matrixen C n er matricen C * søges. Matricerne C k verificerer egenskaben, at C k [ i, j ] = 1, hvis der er en sti fra i til j, der kun passerer gennem hjørner, der er mindre end eller lig med k , og 0 ellers.

Denne karakteristiske egenskab er godt verificeret for k = 0 og for k = n . For at konstruere matricen C k , vi se, at der findes en vej fra jeg til j passerer kun gennem toppunkter mindre end eller lig med k , hvis og kun hvis der findes en vej fra jeg til j passerer kun gennem lavere toppunkter eller lig med k- 1 eller hvis der er en sti fra i til k, der passerer gennem hjørner, der er mindre end eller lig med k-1, og en sti fra k til j passerer gennem hjørner, der er mindre end eller lig med k-1 . Hvad kan formuleres ved:

{\ displaystyle C_ {k} [i, j] = C_ {k-1} [i, j] \ lor (C_ {k-1} [i, k] \ land C_ {k-1} [k, j ])}

Dette princip bruges også i Floyd-Warshall-algoritmen .

Algoritme

Vi kan skrive algoritmen i pseudokode som følger (her er C den tilknyttede matrix i grafen):

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 Cn

Man kan optimere algoritmen ved at udføre beregningen på plads i en enkelt matrix C. Følgende pseudokode udfører denne beregning:

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 C

Det boolske udtryk omskrives med følgende betingelser:

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 C

Dette er nøjagtigt formuleringen af algoritmen, der er offentliggjort i ACM-kommunikationen.

Eksempel på en funktion programmeret i C, som for den binære adjacensmatrix C i den givne graf G beregner adjacency matrix A for 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]); }

Kompleksitet

Opbygningen af den transitive lukning af Warshall-algoritmen har en kompleksitet i . Det kan dog være interessant at oprette den transitive lukning af en graf en gang for alle; man kan således ved simpel inspektion vide, om hjørnerne i og j tilhører den samme tilsluttede komponent i en konstant tid (forbeholdt statiske systemer). $\ Theta (n ^ {3})$

Noter og referencer

(i) Stephen Warshall , " A teorem er booleske matricer " , Journal of the ACM , vol. 9, n o 1,januar 1962, s. 11–12 ( DOI 10.1145 / 321105.321107 )
Bernard Roy , “ Transitivity and Connectivity. ", CR Acad. Sci. Paris , vol. 249,1959, s. 216–218.
(i) Robert W. Floyd , " Algoritme 96: Ancestor " , Communications of the ACM , vol. 5, n o 6,Juni 1962, s. 344-345 ( DOI 10.1145 / 367766.368168 )
Alexander Schrijver beskriver de forskellige bidrag i sin bog: Combinatorial Optmization , Berlin, Springer,2004, 1881 s. ( ISBN 978-3-540-44389-6 , note BNF n o FRBNF39117421 ) , s. 129, kapitel 8 “Korteste stier: vilkårlige længder”, afsnit 8.6g. Historiske noter på de korteste stier: Alle par: Roy, Warshall, Floyd, Dantzig.
" Transitiv lukning: Warshall-algoritme " på University of Quebec i Montreal .

Se også

Forbindelsesalgoritmer baseret på pegepinde (for ikke-rettede grafer)
Floyd-Warshall-algoritme
Korteste sti-problem
Transitiv lukning