floyd-warshall diseño y análisis de algoritmos. luis rodríguez pérez
DESCRIPTION
FLOYD-WARSHALL Diseño y análisis de algoritmos. Luis Rodríguez Pérez. Algoritmo de Floyd-Warshall. Conocido también como la clausura transitiva de un grafo. Entrada: Grafo dirigido/no dirigido, con peso asociado a las aristas. Salida: - PowerPoint PPT PresentationTRANSCRIPT
FLOYD-WARSHALL
Diseño y análisis de algoritmos.
Luis Rodríguez Pérez.
Algoritmo de Floyd-Warshall
Conocido también como la clausura transitiva de un grafo.
Entrada: Grafo dirigido/no dirigido, con peso asociado a las aristas.
Salida: Matriz Dn que entrega el menor camino para ir
de un nodo i a un nodo j del grafo. Matriz Sn que entrega el nodo intermedio para
llegar desde un nodo i a un nodo j del grafo.
Ejemplo:
Tenemos el siguiente grafo:
1
2
5
3
45
4
1510
63
1
2
3
1
4
1 511
2
3
1 51
4
1
3
22 4
5
2
3
2
3
4
3
5
3
42 44
5
4
5
3
55
2
3 10 3 5
10 6 15 5 6 44
D0 1 2 3 4 5
1
2
3
5 4
Ejemplo:
Ahora obtenemos la matriz S0
3 10 3 5
10 6 15 5 6 44
D0 1 2 3 4 5
1
2
3
5 4
2 3 4 51 3 4 5
1 2 4 51 2 3 54
S0 1 2 3 4 5
1
2
3
5 1 2 43
3 10 3 5
10 6 15 5 6 44
D0 1 2 3 4 5
1
2
3
5 4
13 5 13 6 15
4
D1 1 2 3 4 5
1
2
3
5
3 10 3
10
10
3 5
13 < ? 2 3 4 51 3 4 5
1 2 4 5 1 2 3 54
S0 1 2 3 4 5
1
2
3
5 1 2 43
1 4 51 4 5
4
S1 1 2 3 4 5
1
2
3
5
2 3 4 51
1 11
5 6 4
42 3 5
2 43
10
< 5 ?5
< ?
3
10
3
13 < ?6
3
6
< 6 ?15 < 15 ?
Cada vez que hayun en una filao columna esta, no cambia
13 5 13 6 15
4
D1 1 2 3 4 5
1
2
3
5
3 10 3
10
1 4 51 4 5
4
S1 1 2 3 4 5
1
2
3
5
2 3 4 51
1 11
5 6 4
42 3 5
2 43
64
D2 1 2 3 4 5
1
2
3
5
10 8
10 8 6
13 5 13
3
3
5
15
4
4
44
S2 1 2 3 4 5
1
2
3
5
3 2
1 2 3
1 4 51
2
1
2
2
5
5
15
43
3
13
10 16 < 10 ?13
10
58 < ?
Como hay en una fila y una columnaestas se copian igual
3
10 13
53
16 < 10?10
3
6
5
18 < 6?
3
5
5
6
13
8 < ?6
3 13
18 < 6?
64
D2 1 2 3 4 5
1
2
3
5
10 8
10 8 6
13 5 13
3
3
5
15
4
4
44
S2 1 2 3 4 5
1
2
3
5
3 2
1 2 3
1 4 51
2
1
2
2
5
5
15
4 3
4
D3 1 2 3 4 5
1
2
3
5
5
4
S3 1 2 3 4 5
1
2
3
5
8 2
428 33 2
3 125 3
8 5 4 2 2 5
4 21 4
6
10
106
13
13 15
4
3
13
1
1 5
3
Como hay en una fila esta se copia igual.
13
103 23 < 3?3
13 6
8 16< 8?8
6 15
25< ?10
15
13
10
3 23< 3?10
3
6
5 19< 5?6
5
15
28< ?Como en la fila 4todos los numeros sonmenores que la fila pivote(3), queda igual.
4
D3 1 2 3 4 5
1
2
3
5
5
4
S3 1 2 3 4 5
1
2
3
5
8 2
428 33 2
3 125 3
8 5 4 2 2 5
4 21 4
6
10
106
13
13 15
4
3
13
1
1 5
3
4
D4 1 2 3 4 5
1
2
3
5
4
S4 1 2 3 4 5
1
2
3
5
9 43 2
3 112 4
9 412 4
10 3
10 1
2
4
4
45
5
8
8 5 4 2 2
4
66 3
11 4
11 410 4
10 4
8
5
3 13< 3?3
5 6
10 14< 10?10
6 4
25 12< 25?25
4
8
5
8
3 13< 3?
8
3
6
13 11< 13?13
6 4
28 9< 28?28
4
5
8610 14< 1010
8 513 11< 13?15
4513 10< 15?
84
4156
12< ?58
9< ?6
5
10< ?
4
D4 1 2 3 4 5
1
2
3
5
4
S4 1 2 3 4 5
1
2
3
5
9 43 2
3 112 4
9 412 4
10 3
10 1
2
4
4
45
5
8
8 5 4 2 2
4
66 3
11 4
11 410 4
10 4
4
D5 1 2 3 4 5
1
2
3
5
4
S5 1 2 3 4 5
1
2
3
5
3 2
3 110 3
10 1
45
28
8 25 2
46
6 3
11 4
11 4
9 412 4
9 412 4 454
4
10 4
10 4
3
9
12 21< 3?
9
3
10
10 22< 10?10
10 4
816< 8?
8
4
12
9
12
3 21< 3?
10
3
12
11 19< 11?11
10 4
5 13< 5?95
4
10
12
10 22< 10?
12
10
9
11 19< 11?
9
11
4
6 14< 6?10
4
64
128 16< 8?
958
1213< 5?5
9 106 14< 6?