Algoritmo de Floyd-Warshall | ejemplo

Ejemplo

Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:

Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.

1ª Iteración: nodo intermedio = 1

La matriz es simétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.

d23 = min(d23, d21 + d13) = 8

d24 = min(d24, d21 + d14) = 4

d25 = min(d25, d21 + d15) = 9

d26 = min(d26, d21 + d16) =

d32 = min(d32, d31 + d12) = 8

d34 = min(d34, d31 + d14) = 6

d35 = min(d35, d31 + d15) = 7

d36 = min(d36, d31 + d16) = 1

d45 = min(d45, d41 + d15) =

d46 = min(d46, d41 + d16) = 4

d56 = min(d56, d51 + d16) =

La matriz de distancia después de esta iteración es:

2ª Iteración: nodo intermedio = 2

d13 = min(d13, d12 + d23) = 5

d14 = min(d14, d12 + d24) = 1

d15 = min(d15, d12 + d25) = 12

d16 = min(d16, d12 + d26) =

d34 = min(d34, d32 + d24) = 6

d35 = min(d35, d32 + d25) = 7

d36 = min(d36, d32 + d26) = 1

d45 = min(d45, d42 + d25) = 13

d46 = min(d46, d42 + d26) = 4

d56 = min(d56, d52 + d26) =

La matriz de distancia después de esta iteración es:

3ª Iteración: nodo intermedio = 3

d12 = min(d12, d13 + d32) = 3

d14 = min(d14, d13 + d34) = 1

d15 = min(d15, d13 + d35) = 12

d16 = min(d16, d13 + d36) = 6

d24 = min(d24, d23 + d34) = 4

d25 = min(d25, d23 + d35) = 9

d26 = min(d26, d23 + d36) = 9

d45 = min(d45, d43 + d35) = 13

d46 = min(d46, d43 + d36) = 4

d56 = min(d56, d53 + d36) = 8

La matriz de distancia después de esta iteración es:

4ª Iteración: nodo intermedio = 4

d12 = min(d12, d14 + d42) = 3

d13 = min(d13, d14 + d43) = 5

d15 = min(d15, d14 + d45) = 12

d16 = min(d16, d14 + d46) = 5

d23 = min(d23, d24 + d43) = 8

d25 = min(d25, d24 + d45) = 9

d26 = min(d26, d24 + d46) = 8

d35 = min(d35, d34 + d45) = 7

d36 = min(d36, d34 + d46) = 1

d56 = min(d56, d54 + d46) = 8

La matriz de distancia después de esta iteración es:

5ª Iteración: nodo intermedio = 5

d12 = min(d12, d15 + d52) = 3

d13 = min(d13, d15 + d53) = 5

d14 = min(d14, d15 + d54) = 1

d16 = min(d16, d15 + d56) = 5

d23 = min(d23, d25 + d53) = 8

d24 = min(d24, d25 + d54) = 4

d26 = min(d26, d25 + d56) = 8

d34 = min(d34, d35 + d54) = 6

d36 = min(d36, d35 + d56) = 1

d46 = min(d46, d45 + d56) = 4

La matriz de distancia después de esta iteración es:

6ª Iteración: nodo intermedio = 6

d12 = min(d12, d16 + d62) = 3

d13 = min(d13, d16 + d63) = 5

d14 = min(d14, d16 + d64) = 1

d15 = min(d15, d16 + d65) = 12

d23 = min(d23, d26 + d63) = 8

d24 = min(d24, d26 + d64) = 4

d25 = min(d25, d26 + d65) = 9

d34 = min(d34, d36 + d64) = 5

d35 = min(d35, d36 + d65) = 7

d45 = min(d45, d46 + d65) = 12

La matriz de distancia después de esta iteración es:

Ya se han hecho todas las iteraciones posibles. Por tanto, el camino mínimo entre 2 vértices cualesquiera del grafo será el obtenido en la matriz final. En este caso, el camino mínimo entre 3 y 4 vale 5.

Other Languages