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:
5
3
22
4
44
4
6
5
55
11
10
3
33
15
D0 1
1
2 3 4 5
3 10  
 5 
2 3
3 10 
6 15
4  5 6
4
5    4
Ejemplo:
Ahora obtenemos la matriz S0
D0 1
1
2
3
4
5
3
2 3 4 5
3 10  
 5 
10 
6 15
 5 6
4
   4
S0 1
1
2
3
4
5
1
1
2 3 4 5
2 3 4 5
3 4 5
2
4 5
1 2 3
5
1 2 3 4
D0 1 2 3 4 5
3 10  
1
 5 
2 3
3 10 
6 15
4  5 6
4
5    4
13

 << 5??
Cada vez que hay
un  en una fila
o columna
esta,
13<<<15

6
???

no cambia
S0 1
1
2
1
2 3 4 5
2 3 4 5
3 4 5
3 1 2
4 5
4 1 2 3
5
5 1 2 3 4
D1 1 2 3 4 5
3 10  
1
13 5 
2 3
S1 1 2 3 4 5
2 3 4 5
1
1 4 5
2 1
3 10 13
6 15
4  5 6
4
5    4
3 1 1
4 5
4 1 2 3
5
5 1 2 3 4
D1 1
1
2
3
2 3 4 5
3 10  
13 5 
3 10 13
6 15
4  5 6
4
5    4
D2 1
1
2
3
2 3 4 5
3 10 8 
13 5 
3 10 13
6 15
4 8 5 6
4
5    4
S1 1
8 < ?
16
10 ?
Como hay 
en una fila y una
columna
18
16 < 6?
10?
estas se copian igual
818
< ?
< 6?
1
2
1
2 3 4 5
2 3 4 5
1 4 5
3 1 1
4 5
4 1 2 3
5
5 1 2 3 4
S2 1
1
2
3
4
5
1
2 3 4 5
2 3 2 5
1 4 5
1 1
2 2
4 5
3
5
1 2 3 4
D2 1
1
2
3
2 3 4 5
3 10 8 
13 5 
3 10 13
6 15
4 8 5 6
4
5    4
D3 1
1
2
3
2 3 4 5
3 10 8 25
13 5 28
3 10 13
6 15
4 8 5 6
4
5    4
S2 1
16<
23
<8?
3?
25<
?
Como
hay
fila 4
Como
en la3?
23<
28<

19<
en
una
fila5?
esta?se
todos
los
numeros
copia
son igual.
menores que la fila
pivote(3), queda
igual.
1
2
1
2 3 4
2 3 2
1 4
3 1 1
4 2 2
5 1 2
S3 1
1
2
3
4
5
1
4
3
5
5
5
5
3 4
2 3 4
2 3 2
1 4
1 1
2 2
5
5
3
3
4 5
3
5
1 2 3 4
2 3 4 5
33 10
10 8 25
1
13 5 28
2 3
3 10 13
6 15
4 8 5 6
4
5 
 
 4
S3 1
D3 1
14<
13<
3?
12<10?
25?
13<28?
11<
9<
13?
3?
14< 13?
11<
10<
10
15?
12<
?
9<
10<?
?
1
2
1
S4 1
1
2
1
2
3
4
5
5
3
3
3 1 1
4 5
4 2 2 3
5
5 1 2 3 4
D4 1
2 3 4 5
3 10 8 12
3
11 5 9
10 11
6 10
8 5 6
4
12 9 10 4
2 3 4
2 3 2
1 4
3
4
5
2 3 4 5
2 3 2 4
1
4 4 4
1 4
4 4
2 2 3
5
4 4 4 4
D4 1
1
2
3
4
5
2 3 4 5
3 10 8 12
3
11 5 9
10 11
6 10
8 5 6
4
12 9 10 4
D5 1
1
2
3
2 3 4 5
3 10 8 12
11 5 9
3 10 11
6 10
4 8 5 6
4
5 12 9 10 4
22< 8?
16<
10?
21<
3?
21<
19< 3?
13<
11?
5?
14<
22< 6?
19<
10?
11?
13<
16< 5?
14<
8?
6?
S4 1 2 3 4
2 3 2
1
4 4
2 1
3 1 4
4
4 2 2 3
5 4 4 4 4
S5 1
1
2
3
4
5
1
5
4
4
4
5
2 3 4 5
2 3 2 4
4 4 4
1 4
2 2 3
4 4 4
4 4
5
4
Descargar

Algoritmo de Floyd