algorithm
Algoritmo de Floyd-Warshall

Algoritmo de ruta más corta de todos los pares

El algoritmo de Floyd-Warshall es para encontrar rutas más cortas en un gráfico ponderado con ponderaciones de borde positivas o negativas. Una sola ejecución del algoritmo encontrará las longitudes (pesos sumados) de las rutas más cortas entre todos los pares de vértices. Con una pequeña variación, puede imprimir la ruta más corta y puede detectar ciclos negativos en un gráfico. Floyd-Warshall es un algoritmo de programación dinámica.

Veamos un ejemplo. Vamos a aplicar el algoritmo de Floyd-Warshall en este gráfico:

Lo primero que hacemos es tomar dos matrices 2D. Estas son matrices de adyacencia . El tamaño de las matrices será el número total de vértices. Para nuestra gráfica, tomaremos 4 * 4 matrices. La Matriz de distancia almacenará la distancia mínima encontrada hasta ahora entre dos vértices. Al principio, para los bordes, si hay un borde entre uv y la distancia / peso es w , almacenaremos: distance[u][v] = w . Por todos los bordes que no existen, vamos a poner el infinito . La Matriz de ruta es para regenerar la ruta de distancia mínima entre dos vértices. Entonces, inicialmente, si hay una ruta entre u y v , vamos a poner la path[u][v] = u . Esto significa que la mejor manera de llegar al vértice-v del vértice-u es usar el borde que conecta v con u . Si no hay una ruta entre dos vértices, vamos a poner N allí para indicar que no hay una ruta disponible ahora. Las dos tablas para nuestra gráfica se verán como:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Como no hay bucle, las diagonales se configuran en N. Y la distancia desde el propio vértice es 0 .

Para aplicar el algoritmo Floyd-Warshall, vamos a seleccionar un vértice medio k . Luego, para cada vértice i , vamos a verificar si podemos ir de i a k y luego k a j , donde j es otro vértice y minimizar el costo de ir de i a j . Si la distancia actual [i] [j] es mayor que la distancia [i] [k] + distancia [k] [j] , vamos a poner la distancia [i] [j] a la suma de esas dos distancias . Y la ruta [i] [j] se establecerá en la ruta [k] [j] , ya que es mejor ir de i a k , y luego k a j . Todos los vértices serán seleccionados como k . Tendremos 3 bucles anidados: para k yendo de 1 a 4, i va de 1 a 4 y j va de 1 a 4. Vamos cheque:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Entonces, lo que básicamente estamos comprobando es, para cada par de vértices, ¿obtenemos una distancia más corta al atravesar otro vértice? El número total de operaciones para nuestro gráfico será 4 * 4 * 4 = 64 . Eso significa que vamos a hacer este control 64 veces. Veamos algunos de ellos:

Cuando k = 1 , i = 2 y j = 3 , la distancia [i] [j] es -2 , que no es mayor que la distancia [i] [k] + distancia [k] [j] = -2 + 0 = -2 . Así se mantendrá sin cambios. De nuevo, cuando k = 1 , i = 4 y j = 2 , distancia [i] [j] = infinito , que es mayor que la distancia [i] [k] + distancia [k] [j] = 1 + 3 = 4 . Entonces colocamos la distancia [i] [j] = 4 , y colocamos la ruta [i] [j] = ruta [k] [j] = 1 . Lo que esto significa es que, para pasar del vértice 4 al vértice 2 , la ruta 4-> 1-> 2 es más corta que la ruta existente. Así es como poblamos ambas matrices. El cálculo para cada paso se muestra aquí . Después de hacer los cambios necesarios, nuestras matrices se verán como:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Esta es nuestra matriz de distancias más corta. Por ejemplo, la distancia más corta de 1 a 4 es 3 y la distancia más corta entre 4 a 3 es 2 . Nuestro pseudo-código será:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Imprimiendo el camino:

Para imprimir la ruta, revisaremos la matriz de ruta . Para imprimir la ruta de u a v , comenzaremos desde la ruta [u] [v] . Estableceremos seguir cambiando v = ruta [u] [v] hasta que encontremos la ruta [u] [v] = u y empujemos todos los valores de la ruta [u] [v] en una pila. Después de encontrar u, vamos a imprimir u y empiezan a saltar los elementos de la pila e imprimirlas. Esto funciona porque la matriz de ruta almacena el valor del vértice que comparte la ruta más corta a v desde cualquier otro nodo. El pseudocódigo será:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Encontrando el Ciclo del Borde Negativo:

Para saber si hay un ciclo de borde negativo, tendremos que verificar la diagonal principal de la matriz de distancia . Si algún valor en la diagonal es negativo, eso significa que hay un ciclo negativo en la gráfica.

Complejidad:

La complejidad del algoritmo Floyd-Warshall es O (V³) y la complejidad del espacio es: O (V²) .