algoritmo de warshall 1
Post on 05-Jul-2015
1.073 Views
Preview:
TRANSCRIPT
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
top related