← Volver a los ejercicios

La recurrencia de Floyd-Warshall

Un paso del algoritmo agrega un vértice al conjunto de intermedios permitidos y aplica d[i][j] = min(d[i][j], d[i][k] + d[k][j]) a toda la matriz. Aquí se escoge el paso, se marcan las parejas que mejoran y se escoge el valor nuevo de una de ellas antes de ver la matriz que queda.

1. El grafo y el paso

En ámbar, el vértice k que se permite como intermedio. En azul, sus aristas.

2. La matriz antes del paso

Sombreadas, la fila k y la columna k: son las dos entradas que la recurrencia consulta para cada pareja, y las únicas que el paso no puede mover.

3. Marque las parejas que mejoran

Haga clic en cada casilla que baja en este paso. Vuelva a hacer clic para quitarla. La diagonal aparece con un punto porque sin ciclos negativos se queda en 0.

4. El valor nuevo

5. La matriz después del paso

6. Para llevarse

Sin solución aquí. Tome el grafo de cinco vértices y recorra los pasos de k = 0 a k = 4 contando cuántas parejas mejoran en cada uno. Después cambie el orden de los vértices en su cabeza, permitiendo primero el 4 y de último el 0, y diga cuáles pasos mejoran ahora y si la matriz final es la misma.