Algoritmo Floyd-Warshall: Guía de entrevistas de codificación

TL;DR: El algoritmo Floyd-Warshall calcula los caminos más cortos de todos los pares con programación dinámica. Inicialice una matriz de distancias del gráfico, luego, para cada vértice intermedio k, actualice cada par con dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Se ejecuta en tiempo O(V³) y espacio O(V²) y puede exponer ciclos negativos a través de entradas diagonales negativas.

¿Qué es el algoritmo Floyd-Warshall?

Floyd-Warshall es un algoritmo de programación dinámica para caminos más cortos entre cada par ordenado de vértices. Funciona con gráficos ponderados dirigidos o no dirigidos y permite aristas negativas. Sin embargo, si existe un ciclo relevante de peso negativo, algunos caminos más cortos no tienen un mínimo finito porque atravesar repetidamente el ciclo sigue reduciendo el costo del camino.

El algoritmo es memorable porque convierte un problema de ruta global en una sola decisión: para el vértice intermedio actual k, ¿es mejor la ruta más conocida de i a j tal como está, o ir de i a k y luego de k a j?

¿Cómo se deriva la recurrencia?

Defina D(k, i, j) como la distancia más corta de i a j cuyos vértices intermedios pueden provenir sólo de los primeros k vértices. Una ruta permitida más corta evita el vértice k, manteniendo D(k−1, i, j), o usa k y se divide en la mejor ruta permitida de i a k ​​más la mejor ruta permitida de k a j.

Eso da la recurrencia:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Debido a que la etapa k depende solo de los valores de la etapa k−1 de manera compatible, la matriz se puede actualizar en el lugar. Este razonamiento también explica el orden de los bucles críticos: k debe ser el bucle más externo. Poner i o j afuera cambia el invariante y puede usar rutas parcialmente permitidas de manera incorrecta.

¿Cómo se inicializa la matriz de distancias?

Crea una matriz V por V. Establezca dist[i][i] en cero, establezca la celda de un borde directo en su peso y use infinito cuando no exista un borde directo. Si es posible tener bordes paralelos, mantenga el peso directo más pequeño. Antes de sumar dos distancias, verifique que ambas sean finitas para que un centinela infinito no se desborde ni cree un candidato falso.

¿Cómo se rastrea a Floyd-Warshall en una entrevista?

Etiquete las filas de la matriz como fuentes y las columnas como destinos. Muestre la matriz inicial, luego elija una k y evalúe las celdas representativas. Para cada celda, compare el valor actual con la ruta a través de k. Actualice solo cuando ambos segmentos sean accesibles y la nueva suma sea menor.

Normalmente no es necesario dibujar todas las matrices para un ejemplo grande. Trace suficientes celdas para demostrar la invariante, incluida una mejora y un valor sin cambios. Indique que después de completar k, cada entrada de la matriz es óptima entre caminos cuyos vértices intermedios están limitados al conjunto procesado.

¿Qué pseudocódigo deberías escribir?

Utilice tres bucles anidados con k en el exterior:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Explique las comprobaciones finitas y el tipo numérico. En lenguajes con un centinela entero grande, agregar infinito a un valor negativo puede parecer finito o desbordado. Una guardia es parte de la corrección, no simplemente un detalle de implementación.

¿Cuáles son las complejidades del tiempo y el espacio?

Los tres bucles examinan cada combinación de k, i y j, por lo que el tiempo de ejecución es O(V³). La matriz de distancias ocupa el espacio O(V²). La actualización in situ evita una tabla tridimensional, mientras que una matriz de siguiente salto o predecesora para la reconstrucción de rutas agrega O(V²) más espacio.

Floyd-Warshall suele resultar atractivo para gráficos modestos y densos porque su implementación es compacta y predecible. Para un gráfico grande y disperso con aristas no negativas, ejecutar Dijkstra desde cada fuente puede ser más eficiente. Compare siempre la salida requerida, la densidad del gráfico, las restricciones de peso y el recuento de vértices antes de elegir.

¿Cómo se reconstruye el camino más corto real?

Las distancias por sí solas no revelan la secuencia de vértices. Mantenga una matriz next[i][j] inicializada en j cuando exista un borde directo de i a j. Siempre que el enrutamiento a través de k mejore dist[i][j], establezca next[i][j] en next[i][k]. Para reconstruir una ruta, muévase repetidamente desde el vértice actual a next[current][destination] hasta llegar al destino.

Compruebe si hay pares inalcanzables antes de la reconstrucción y protéjase contra casos de ciclo negativo. Si un par puede viajar a un ciclo negativo y luego llegar al destino, no existe un camino finito más corto para reconstruir.

¿Cómo detecta Floyd-Warshall los ciclos negativos?

Una vez finalizado el algoritmo, inspeccione la diagonal. Un valor dist[v][v] < 0 demuestra que se puede alcanzar un ciclo de peso negativo desde v y que puede regresar a v. Esto es más fuerte que simplemente encontrar una ventaja negativa; Pueden existir aristas negativas en gráficos con caminos más cortos perfectamente válidos.

Si el entrevistador pregunta qué pares se ven afectados, identifique cada i y j para los cuales i pueda alcanzar tal vértice v y v pueda alcanzar j. Esos pares pueden recorrer el ciclo negativo muchas veces arbitrariamente, por lo que el valor de su camino más corto no es finito.

¿Cuándo debería elegir otro algoritmo de ruta más corta?

Utilice la búsqueda en amplitud para gráficos no ponderados, Dijkstra para problemas de fuente única con pesos no negativos y Bellman-Ford para una fuente única cuando los pesos negativos o la detección de ciclo negativo alcanzable sean importantes. Floyd-Warshall es la elección directa cuando se requieren distancias de todos los pares y el tiempo cúbico es aceptable.

¿Qué errores en la entrevista deberías evitar?

No coloque k dentro de otro bucle, no olvide los ceros en la diagonal, no agregue infinito sin protección, no confunda aristas negativas con ciclos negativos ni afirme que el espacio matricial O(V²) incluye la entrada automáticamente en cada representación. Aclare si el gráfico está dirigido, si existen aristas paralelas y si el entrevistador necesita distancias, caminos o pares afectados por el ciclo.

Practique el flujo de trabajo del asistente de entrevista de codificación, compare el algoritmo Bellman-Ford y revise la hoja de trucos de complejidad de Big O.

Preguntas frecuentes

Practica el invariante, no solo los bucles

YesToTheOffer puede ayudar a estructurar una explicación de codificación, fundamentarla en sus notas de preparación privadas, examinar casos extremos y conservar la transcripción de la entrevista para su posterior revisión.