Floyd Warshall Algorithm

MedioCaminos más cortos Programación dinámica

+10

Se proporciona un grafo dirigido con n nodos, numerados del 0 al n-1, como una matriz de n por n: matrix[i][j] es el peso de la arista desde el nodo i hasta el nodo j, o -1 cuando no hay ninguna, y matrix[i][i] es 0. La longitud de un camino es la suma de los pesos de sus aristas.

Devuelve una matriz de n por n cuya entrada [i][j] es la longitud del camino más corto desde el nodo i hasta el nodo j, o -1 cuando no se puede llegar al nodo j desde el nodo i.

Función

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: los pesos de las aristas: matrix[i][j] es el peso de la arista de i a j, o -1 cuando no hay ninguna
Devuelveinteger-2d-array: la distancia más corta para cada par de nodos, -1 cuando no hay ningún camino

Restricciones

1 ≤ n ≤ 100, donde n = matrix.length = matrix[i].length
matrix[i][i] = 0
Para i ≠ j, matrix[i][j] es -1 (sin arista) o 0 ≤ matrix[i][j] ≤ 1000.
Las aristas son unidireccionales: matrix[i][j] y matrix[j][i] son independientes.

Ejemplos

Entrada: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Salida: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Explicación: A través del nodo 1, el nodo 0 llega al nodo 2 por 6 en lugar de 11, y al nodo 3 por 9. El nodo 1 llega al nodo 0 a través del nodo 2 por 3. No sale nada del nodo 3, así que su fila es -1 fuera de la diagonal.

Entrada: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Salida: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Explicación: La arista de 2 a 1 tiene un peso de 0, así que 0 → 2 → 1 cuesta 1, menos que el 6 directo. Ninguna arista sale del nodo 1 ni entra en el nodo 0, así que esos pares siguen siendo -1.

Para ir más allá

Después de construir la tabla, una arista se vuelve más barata. ¿Puedes actualizar cada distancia en O(n²) en lugar de volver a ejecutar los bucles O(n³)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Necesitas el camino más corto para cada par de nodos. Floyd-Warshall encuentra las n² respuestas con un solo bucle triple. Cada ronda permite que las rutas pasen por un nodo más y cuesta una comparación por cada par: la mejor ruta hasta el momento frente a la ruta que pasa por el nuevo nodo.

Extiende cada ruta en una arista hasta que nada cambie

Correcto, pero no termina con las pruebas más grandes

Intuición

Empieza con la matriz y, en cada pasada, extiende cada ruta con una arista: una ruta de i a m más la arista m → j es una ruta de i a j, que se conserva si es más corta. Repite hasta que una pasada no cambie nada.

Después de p pasadas, se encuentra toda ruta más corta de hasta p+1 aristas. Ningún peso es negativo, así que alguna ruta más corta no tiene ciclos y tiene como máximo n-1 aristas, y las pasadas terminan con todas las distancias definitivas. Una pasada requiere n³ = 10^6 pasos para 100 nodos, y una cadena larga de rutas más cortas necesita hasta n pasadas: O(n⁴), hasta 10^8 pasos.

Algoritmo

Copia matrix en dist.
Para cada i, m y j: si existen tanto dist[i][m] como matrix[m][j], calcula su suma.
Si dist[i][j] es -1 o mayor que la suma, guarda la suma y recuerda que esta pasada cambió algo.
Repite la pasada hasta que no cambie nada; después, devuelve dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: permite una parada más por ronda

Intuición

Limita los nodos en los que una ruta puede detenerse entre sus extremos. La tabla comienza como la matriz, con las rutas sin paradas. Después de la ronda k, dist[i][j] es la ruta más corta cuyas paradas están todas entre los nodos 0 y k, y la última ronda da la respuesta.

En la ronda k, la mejor ruta que también puede detenerse en k o bien omite k, y la tabla ya la contiene, o bien pasa por k una vez, ya que ningún peso es negativo. Sus dos mitades solo se detienen en los nodos 0 a k-1, así que son dist[i][k] y dist[k][j].

En el primer ejemplo, la ronda 1 reemplaza la ruta directa de 11 desde el nodo 0 hasta el nodo 2 por una de 6. La ronda 2 da una ruta del nodo 0 al nodo 3 de 6 + 3 = 9, con la parada en el nodo 1 dentro del tramo de 6.

Basta con una tabla: la fila k y la columna k no cambian en la ronda k, porque dist[k][k] es 0.

Algoritmo

Copia matrix en dist; -1 significa que aún no se ha encontrado ninguna ruta.
Para k desde 0 hasta n-1, y para cada i y j: omite el par si dist[i][k] o dist[k][j] es -1.
De lo contrario, calcula via = dist[i][k] + dist[k][j].
Si dist[i][j] es -1 o mayor que via, asígnale via.
Devuelve dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Errores comunes y casos límite

Sumar -1 como si fuera un peso: -1 + 5 = 4 parece una ruta. Comprueba primero ambas partes y trata un -1 en dist[i][j] como peor que cualquier ruta.
Colocar dentro el bucle sobre k. Las rutas a través de las paradas 0 a k-1 deben estar definidas antes de ofrecer el nodo k.
Usar el entero más grande como infinito: sumar dos desborda un entero de 32 bits y da una distancia negativa. Una distancia real es como máximo 99 × 1000 = 99,000, así que 10^9 es seguro, ya que 2 × 10^9 es menor que 2^31-1.
Suponer que las aristas van en ambos sentidos. En el segundo ejemplo, el nodo 0 llega al nodo 1, pero desde el nodo 1 no se llega a ningún nodo.
Ejecutar una búsqueda en anchura, que ignora los pesos: en el primer ejemplo, informa que la distancia del nodo 0 al nodo 2 es 11, no 6.

Preguntas frecuentes3

¿Cuál es la complejidad temporal del algoritmo de Floyd-Warshall?

Tiempo O(n³) para n nodos: tres bucles anidados sobre los nodos, con una suma y una comparación por paso, 10^6 pasos para 100 nodos. El espacio es O(n²) para la tabla de distancias, que se puede actualizar in situ.

¿Funciona Floyd Warshall con pesos de arista negativos?

Sí, siempre que no haya un ciclo negativo, es decir, un ciclo cuyos pesos sumen menos de 0. Si hay un ciclo negativo, los caminos más cortos no están definidos, y la tabla lo muestra: algunos dist[i][i] terminan siendo menores que 0.

¿Cuándo deberías usar Floyd Warshall en lugar del algoritmo de Dijkstra?

Usa Floyd-Warshall para cada par de nodos en un grafo denso de hasta unos pocos cientos de nodos. Dijkstra desde cada nodo cuesta O(n³) con un arreglo y O(n · E log n) con un montículo, lo que resulta más eficiente en grafos grandes y dispersos. Floyd-Warshall no necesita montículo y acepta aristas negativas, a diferencia de Dijkstra.

def shortestDistances(matrix):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Salida Esperada

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]