Please enable JavaScript.
Coggle requires JavaScript to display documents.
(Algoritmo de Floyd-Warshall) - Coggle Diagram
Algoritmo de Floyd-Warshall
Definición
Algoritmo para encontrar el camino más corto entre todos los pares de nodos en un grafo
Funciona tanto para grafos dirigidos como no dirigidos
Es un algoritmo de programación dinámica
Objetivo
Calcular las distancias mínimas entre todos los pares de vértices
Detectar caminos más cortos incluso cuando hay caminos intermedios
Características
Complejidad: O(n³), donde n es el número de nodos
Usa una matriz de distancias que se actualiza progresivamente
Soporta pesos negativos, pero no ciclos negativos
Estrategia
Inicializar la matriz de distancias con los pesos del grafo
Para cada nodo intermedio k
Para cada par de nodos (i, j)
Actualizar la distancia de i a j con:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Ventajas
Proporciona distancias mínimas entre todos los nodos
Simple y directo para grafos densos
Desventajas
Lento para grafos muy grandes
No funciona si hay ciclos de peso negativo
Ejemplo práctico
Grafo con 4 nodos: A, B, C, D
Aristas con pesos:
A-B (3)
A-C (INF)
A-D (7)
B-C (1)
B-D (INF)
C-D (2)
Matriz inicial (INF representa infinito)
| | A | B | C | D |
| A | 0 | 3 | ∞ | 7 |
| B | ∞ | 0 | 1 | ∞ |
| C | ∞ | ∞ | 0 | 2 |
| D | ∞ | ∞ | ∞ | 0 |
Proceso
Paso 1: Usar A como nodo intermedio (k = A)
No mejora ningún camino
Paso 2: Usar B como nodo intermedio
A-C mejora: A-B-C = 3 + 1 = 4
Paso 3: Usar C como nodo intermedio
A-D mejora: A-B-C-D = 3 + 1 + 2 = 6
B-D mejora: B-C-D = 1 + 2 = 3
Paso 4: Usar D como nodo intermedio
No mejora ningún camino
Matriz final
| | A | B | C | D |
| A | 0 | 3 | 4 | 6 |
| B | ∞ | 0 | 1 | 3 |
| C | ∞ | ∞ | 0 | 2 |
| D | ∞ | ∞ | ∞ | 0 |
Conclusión
El algoritmo de Floyd-Warshall encuentra todos los caminos más cortos entre todos los nodos
Ideal para grafos densos y cuando se necesita saber la distancia mínima entre cada par de nodos