ALGORITMO DE WARSHALL

• Encuentra si es posible un camino entre cada uno de los vértices de la gráfica dirigida. Es decir no presenta las distancias entre los vértices.

• Se basa en un concepto llamado cerradura transitiva de la matriz de adyacencia.

ALGORITMO DE WARSHALL

Sea la gráfica dirigida G(V,A) y su matriz de adyacencia M. donde

M[i,j]=1 Si existe un arco de I a j M[ij]=0 Si no existe arco de I a j

ALGORITMO DE WARSHALLALGORITMO DE WARSHALL

AB

C

D

MATRIZMATRIZ

AA BB CC DD

AA 00 11 00 00

BB 00 00 11 00

CC 11 00 00 11

DD 00 00 00 00

PIVOTE APIVOTE A

AA BB CC CC

AA 00 11 00 00

BB 00 00 11 00

CC 11 11 00 11

CC 00 00 00 00

PIVOTE BPIVOTE B

AA BB CC DD

AA 00 11 11 00

BB 00 00 11 00

CC 11 11 11 11

DD 00 00 00 00

PIVOTE C

A B C D

A 1 1 1 1

B 1 1 1 1

C 1 1 1 1

C 0 0 0 0

Por Carmen Nereira