El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

El Algoritmo de Floyd-Warshall es un algoritmo clásico utilizado para encontrar las distancias más cortas entre todos los pares de nodos en un grafo ponderado. Este algoritmo es especialmente útil en grafos densos y es conocido por su simplicidad y eficiencia en términos de programación.

Conceptos Básicos

Antes de profundizar en el algoritmo, es importante entender algunos conceptos clave:

Grafo Ponderado: Un grafo donde cada arista tiene un peso asociado, que representa el costo o la distancia entre dos nodos.
Matriz de Adyacencia: Una representación del grafo en forma de matriz, donde el valor en la posición (i, j) representa el peso de la arista que conecta el nodo i con el nodo j.
Distancia Mínima: La menor suma de pesos de las aristas que conectan dos nodos.

Descripción del Algoritmo

El Algoritmo de Floyd-Warshall utiliza una técnica de programación dinámica para actualizar iterativamente una matriz de distancias mínimas. La idea principal es considerar todos los pares de nodos y verificar si una ruta intermedia a través de otro nodo ofrece una distancia menor que la ruta directa.

Pasos del Algoritmo

Inicialización:
- Crear una matriz dist donde dist[i][j] es el peso de la arista entre el nodo i y el nodo j. Si no hay arista, se inicializa con un valor infinito.
- Para cada nodo i, dist[i][i] se inicializa a 0.
Actualización Iterativa:
- Para cada nodo intermedio k, actualizar la matriz dist de manera que dist[i][j] sea el mínimo entre dist[i][j] y dist[i][k] + dist[k][j].

Pseudocódigo

def floyd_warshall(graph):
    # Número de nodos en el grafo
    n = len(graph)
    
    # Inicializar la matriz de distancias
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Configurar las distancias iniciales
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # Actualizar las distancias
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Ejemplo Práctico

Consideremos un grafo con 4 nodos y la siguiente matriz de adyacencia:

	0	1	2	3
0	0	3	∞	7
1	8	0	2	∞
2	5	∞	0	1
3	2	∞	∞	0

Aplicando el Algoritmo de Floyd-Warshall, obtenemos la siguiente matriz de distancias mínimas:

	0	1	2	3
0	0	3	5	6
1	7	0	2	3
2	5	8	0	1
3	2	5	7	0

Ejercicio Práctico

Ejercicio: Implementa el Algoritmo de Floyd-Warshall para el siguiente grafo representado por su matriz de adyacencia:

	0	1	2	3	4
0	0	4	∞	∞	∞
1	∞	0	3	∞	∞
2	∞	∞	0	2	∞
3	∞	-1	∞	0	2
4	∞	∞	∞	∞	0

Solución:

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != float('inf'):
                dist[i][j] = graph[i][j]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, 4, float('inf'), float('inf'), float('inf')],
    [float('inf'), 0, 3, float('inf'), float('inf')],
    [float('inf'), float('inf'), 0, 2, float('inf')],
    [float('inf'), -1, float('inf'), 0, 2],
    [float('inf'), float('inf'), float('inf'), float('inf'), 0]
]

distances = floyd_warshall(graph)
for row in distances:
    print(row)

Salida Esperada

[0, 4, 7, 9, 11]
[inf, 0, 3, 5, 7]
[inf, inf, 0, 2, 4]
[inf, -1, 2, 0, 2]
[inf, inf, inf, inf, 0]

Conclusión

El Algoritmo de Floyd-Warshall es una herramienta poderosa para encontrar las distancias más cortas entre todos los pares de nodos en un grafo ponderado. Su implementación es directa y se basa en la técnica de programación dinámica. Aunque su complejidad temporal es O(n^3), lo que puede ser costoso para grafos muy grandes, sigue siendo una opción eficiente para grafos densos y de tamaño moderado.

Algoritmo de Floyd-Warshall

Conceptos Básicos

Descripción del Algoritmo

Pasos del Algoritmo

Pseudocódigo

Ejemplo Práctico

Ejercicio Práctico

Salida Esperada

Conclusión

Curso de Análisis y Diseño de Algoritmos

Módulo 1: Introducción a los Algoritmos

Módulo 2: Análisis de Algoritmos

Módulo 3: Estrategias de Diseño de Algoritmos

Módulo 4: Algoritmos Clásicos

Módulo 5: Optimización de Algoritmos

Módulo 6: Prácticas y Ejercicios

	0	1	2	3	4
0	0	4	∞	∞	∞
1	∞	0	3	∞	∞
2	∞	∞	0	2	∞
3	∞	-1	∞	0	2
4	∞	∞	∞	∞	0

	0	1	2	3	4
0	0	4	∞	∞	∞
1	∞	0	3	∞	∞
2	∞	∞	0	2	∞
3	∞	-1	∞	0	2
4	∞	∞	∞	∞	0

	0	1	2	3	4
0	0	4	∞	∞	∞
1	∞	0	3	∞	∞
2	∞	∞	0	2	∞
3	∞	-1	∞	0	2
4	∞	∞	∞	∞	0