0Pricing
Coding Interview Prep · Lección

Floyd-Warshall: caminos mínimos entre todos los pares

Rellene la matriz de distancias entre todos los pares mediante el algoritmo de Floyd-Warshall con tres bucles anidados y aplíquelo para encontrar el menor número de saltos entre todos los pares de nodos.

Floyd-Warshall: caminos mínimos entre todos los pares es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

Caminos más cortos entre todos los pares

Floyd-Warshall calcula los caminos más cortos entre cada par de nodos de un grafo ponderado, incluidos los grafos con aristas de peso negativo, pero no los que contienen ciclos negativos. Ejecutar Dijkstra desde cada origen cuesta O(V × (V+E) log V); Floyd-Warshall se ejecuta en O(V³), independientemente de la densidad del grafo. En grafos densos con V ≤ 500, Floyd-Warshall suele ser más sencillo y tener una velocidad comparable.

La idea fundamental: nodos intermedios

La idea clave de Floyd-Warshall es la siguiente: dp[i][j][k] = camino más corto desde i hasta j utilizando únicamente los nodos {0, 1, ..., k} como intermedios. El camino más corto utiliza el nodo k como intermedio o no lo utiliza. Si lo utiliza: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Si no: dp[i][j][k] = dp[i][j][k-1]. Como la tercera dimensión solo avanza, puede eliminarse: actualizamos la matriz in situ.

Inicialización de la matriz de distancias

Comience con una matriz V×V: dist[i][i] = 0 (distancia propia cero), dist[i][j] = weight para las aristas directas y dist[i][j] = inf para las parejas sin arista. Después, itere sobre todos los nodos intermedios k y actualice las parejas (i, j). El bucle exterior sobre k debe ir primero para construir correctamente los caminos a través de un conjunto cada vez mayor de nodos intermedios permitidos.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Implementación completa con ejemplo

Analicemos Floyd-Warshall en un grafo de 4 nodos. Después de procesar cada nodo intermedio k, la matriz se completa con caminos más cortos que pasan por el nodo k. El algoritmo gestiona de forma natural los múltiples saltos al construir los caminos más cortos de manera incremental.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

Detección de ciclos negativos

Después de ejecutar Floyd-Warshall, compruebe la diagonal principal: si algún dist[i][i] < 0, existe un ciclo negativo que pasa por el nodo i. Esto se debe a que un ciclo negativo permite llegar a i desde i con un coste negativo. Si no existe ningún ciclo negativo, todas las entradas de la diagonal permanecen en 0.

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

Reconstrucción del camino

Para reconstruir el camino real desde i hasta j, mantenga una matriz next[i][j]: inicialmente, next[i][j] = j para las aristas directas. Al actualizar a través del nodo intermedio k, establezca next[i][j] = next[i][k]. Para recuperar el camino, comience en i y siga los punteros de next hasta llegar a j. Esto añade un espacio O(V²) y un coste O(V) por reconstrucción del camino.

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

Cierre transitivo

Una variante más sencilla: el cierre transitivo responde a «¿se puede llegar al nodo j desde el nodo i?» para todos los pares. Sustituya las distancias por valores booleanos: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Esto es Floyd-Warshall utilizando OR booleano en lugar de suma y mínimo. Inicialice reach[i][i] = True y reach[i][j] = True para las aristas directas.

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

Complejidad y cuándo usarlo

Floyd-Warshall: tiempo O(V³), espacio O(V²). Para grafos densos (E ≈ V²) con V ≤ 300, es más rápido que ejecutar Dijkstra V veces, que también cuesta O(V³) en ese caso. Para grafos dispersos con V = 1000 y E = 3000, ejecutar Dijkstra V veces cuesta O(V×E×log V) ≈ 33M, mientras que Floyd-Warshall cuesta O(V³) = 10⁹; gana Dijkstra. Sepa cuándo corresponde utilizar cada algoritmo.

Número mínimo de saltos entre todos los pares

Establezca todos los pesos de las aristas en 1 (o use una matriz de adyacencia booleana con Floyd-Warshall utilizando la suma en lugar de min): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Esto calcula el número mínimo de saltos entre todos los pares: el resultado de un BFS para todos los pares, pero calculado mediante una única pasada de Floyd-Warshall de O(V³).

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

Contexto de entrevista: cuándo los entrevistadores preguntan por Floyd-Warshall

Floyd-Warshall aparece en entrevistas en preguntas que implican: (1) distancias entre todos los pares en un grafo pequeño, (2) determinar si existe algún ciclo con peso total negativo, (3) calcular rutas más cortas en problemas de propagación de restricciones y (4) problemas que solicitan explícitamente soluciones O(V³) donde V ≤ 200. Mencione siempre la estructura de tres bucles y el requisito de que no haya ciclos negativos para que sea correcto.

G​​rafos no dirigidos con Floyd-Warshall

Para los grafos no dirigidos, añada ambas direcciones para cada arista: dist[u][v] = dist[v][u] = weight. El resto del algoritmo es idéntico. La matriz resultante es simétrica: dist[i][j] == dist[j][i] para todos los pares. Al inicializarla, tenga cuidado de no asignar accidentalmente aristas dirigidas: las aristas no dirigidas deben añadirse en ambas direcciones a la matriz inicial antes de ejecutar los tres bucles.

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Resumen de la lección

En esta lección ha aprendido: Floyd-Warshall calcula las rutas más cortas entre todos los pares mediante tres bucles anidados y la recurrencia dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), los ciclos negativos se pueden detectar comprobando si algún dist[i][i] < 0 después de finalizar y el algoritmo se ejecuta en tiempo O(V³) y utiliza un espacio O(V²). A continuación, retomará las aplicaciones de las rutas más cortas con Network Delay Time y las técnicas de reconstrucción de rutas.

Preguntas frecuentes

¿La lección «Floyd-Warshall: caminos mínimos entre todos los pares» es gratis?

Sí — el texto completo de «Floyd-Warshall: caminos mínimos entre todos los pares» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «Floyd-Warshall: caminos mínimos entre todos los pares»?

Rellene la matriz de distancias entre todos los pares mediante el algoritmo de Floyd-Warshall con tres bucles anidados y aplíquelo para encontrar el menor número de saltos entre todos los pares de no… Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.

¿Cuánto tiempo toma la lección «Floyd-Warshall: caminos mínimos entre todos los pares»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Algoritmo de Dijkstra con una cola de prioridad
  2. Bellman-Ford y ciclos negativos
  3. Floyd-Warshall: caminos mínimos entre todos los pares
  4. Network Delay Time y reconstrucción de caminos
← Volver a Coding Interview Prep