Dado un gráfico ponderado de N nodos, ¿existe un algoritmo que calcule la ruta más corta entre todos los nodos?

Floyd-Warshall, también conocido como Roy-Warshall, es un algoritmo de ruta más corta de todos los pares (APSP) desarrollado por Robert Floyd, Bernard Roy y Stephen Warshall. Es un ejemplo de programación dinámica que utiliza 3 bucles anidados. A un costo O (| V | ^ 3) , es bastante impresionante, dado que Bellman-Ford podría encontrar el mismo costo ( O (| V || E |) ) para encontrar solo la ruta más corta de fuente única (SSSP) para densos gráfico que tiene | V | ^ 2 aristas. Floyd-Warshall puede trabajar con bordes negativos al igual que Bellman-Ford. Después de todo, ambos se basan en programación dinámica. En cuanto a la detección del ciclo negativo, una vez más, ambos pueden detectarlo. Sin embargo, en presencia de un ciclo negativo, los resultados de ambos no son válidos.

Tres bucles anidados

dist [] [] // matriz de ruta más corta
p [] [] // matriz predecesora, utilizada para reconstruir la ruta

dist [] [] = ∞

para cada vértice i
dist [i] [i] = 0

para cada borde (i, j)
dist [i] [j] = peso (i, j)
p [i] [j] = j

para k = 1 a | V |
para i = 1 a | V |
para j = 1 a | V |
si dist [i] [j]> dist [i] [k] + dist [k] [j]
dist [i] [j] = dist [i] [k] + dist [k] [j]
p [i] [j] = p [i] [k]

Para calcular la ruta más corta entre cualquier par ( s , t ), hemos considerado cada uno de los | V | vértices como puntos intermedios k , y eligió el más barato entre i) existente ( s , t ) y ii) la suma de s a k y luego de k a t, lo que significa s a t a través de k .

¿Cortocircuitar un SSSP?

¿Significa que podemos derivar una solución SSSP para cualquier par (s, t), a un costo de O (| V | ^ 2)? Para ser precisos, ¿podemos hacer lo siguiente?

para k = 1 a | V |
si dist [i] [j]> dist [i] [k] + dist [k] [j]
dist [i] [j] = dist [i] [k] + dist [k] [j]

Después de todo, nos hemos relajado a través de todos los nodos intermedios. Bueno, eso no funcionará! ¿Por qué?

Programación dinámica

Si queremos obtener el camino más corto entre ( i , j ) usando k (1 a k ) nodos intermedios, entonces tenemos que elegir el más barato entre los siguientes caminos:

  1. Sin usar k : dist [ i ] [ j ] usando nodos intermedios 1 a k -1.
  2. Usando k : dist [ i ] [ k ] + dist [ k ] [ j ], donde dist [ i ] [ k ] y dist [ j ] [ k ] deben utilizar los nodos intermedios 1 a k-1 .

En k = 0, dist [] [] se inicializa utilizando pesos de borde donde existe, 0 para diagonales (dist [ v ] [ v ]) e infinito para los restos.

Un ejemplo

Supongamos que queremos calcular dist [2] [3] cuando k = 5.

Entonces, dist [2] [3] = min {dist [2] [3], dist [2] [5] + dist [5] [3]}

Aquí, las tres distancias: dist [2] [3], dist [2] [5] y dist [5] [3] ya deben usar los nodos intermedios 1 a 4. Es decir, dist [2] [5] no es el costo estático establecido en k = 0; posiblemente el costo de borde, 0 o infinito. Por el contrario, dist [2] [5] ya se calcula usando k de 1 a 4. Del mismo modo, dist [5] [3] (y dist [2] [3] también) se calcula usando k de 1 a 4.

En otras palabras, no podemos calcular un cierto dist [ s ] [ t ] solo, usando los nodos intermedios 1 a k . En vez de cada nodo intermedio k, necesitamos calcular dist [ i ] [ j ] progresivamente, usando los 3 bucles anidados, como se muestra anteriormente.

Obviamente podemos usar la recursividad sin los bucles. Eso no nos ahorrará ningún trabajo. De hecho, mientras usamos la recursividad, si no estamos reutilizando las soluciones existentes para los subproblemas, repetiremos el cálculo, algo muy costoso.

Reconstrucción de caminos

La matriz predecesora p, realiza un seguimiento de la ruta más corta. Si tenemos que encontrar la mejor ruta de s a t , sabemos con certeza que comenzamos con s . Imprimimos s . Para saber a dónde fuimos desde allí, tenemos que mirar p [ s ] [ t ]. Si eso es t , hemos terminado ya que ese es el destino. Sin embargo, si ese no es el caso, significa que encontramos otro nodo r. Entonces sabemos por s que fuimos a un nodo intermedio r . Entonces esto se convierte en el nuevo comienzo para el resto del camino. Sin embargo, el destino sigue siendo el mismo t . Nuevamente miramos p [ s ] [ t ] y continuamos igual hasta llegar a t, todo el tiempo imprimiendo r (= p [s] [t]) .

Ajuste de los cambios de peso del borde

¿Qué pasa si el peso de un borde cambia (aumenta o disminuye)? ¿Necesitamos volver a calcular APSP desde cero? ¿O podemos ajustar los resultados existentes usando algunos cálculos parciales?

Esta publicación apareció originalmente como Algoritmo Floyd-Warshall en mi blog Sharing Experiences ( gopalcdas dot com ).

Adición de nodo incremental

Supongamos que a partir de ahora, tenemos 4 nodos y se calcula APSP. En este punto llega el quinto nodo, junto con algunos bordes que conectan los nodos existentes. En lugar de calcular APSP desde cero, a un costo de O (| V | 3) = O (125) , podemos usar el APSP ya calculado y extenderlo para completarlo para 5 nodos, a un costo de O (| V | ^ 2) = O (25) .

Esto se explica a continuación a través de una solución de JLTI Code Jam – Jan 2018 problema.

El ciclo negativo se puede identificar al observar las diagonales de la matriz dist [] [] generada por el algoritmo Floyd-Warshall. Después de todo, el valor diagonal dist [2] [2] es menor que 0 significa que una ruta que comienza desde 2 y termina en 2 da como resultado un ciclo negativo: existe un arbitraje.

Sin embargo, se nos pide calcular de manera incremental lo mismo, a costa de O (n ^ 2) para cada nuevo vértice. El algoritmo Floyd-Warshall toma O (n ^ 3) tiempo para calcular la ruta más corta de todos los pares (APSP), donde n es el número de vértices. Sin embargo, dado que ya calculó APSP para n nodos, cuando llega el (n + 1) th nodo, puede reutilizar el resultado existente y extender APSP para acomodar el nuevo nodo incrementalmente a un costo de O (n ^ 2).

Esta es la solución para JLTI Code Jam – Ene 2018.

Tasas de conversión

Si la tasa de USD a SGD es r1 y la tasa de SGD a GBP es r2, para obtener la tasa de USD a GBP, multiplicamos las dos tasas y obtenemos la nueva tasa que es r1 * r2. Nuestro objetivo es maximizar la tasa, que es maximizar r1 * r2.

En el algoritmo de rutas, hablamos de minimizar el costo de la ruta (suma). Por lo tanto, maximizar la multiplicación de tasas (r1 * r2) se traduciría en minimizar 1 / (r1 * r2) => log (1 / (r1 * r2)) => log (r1 * r2) -1 => – log r1 – log r2 => (–log r1) + (–log r2) => suma de (–log r1) y (–log r2). La tasa r1 debe convertirse en – log r1 y eso es lo que necesitamos usar en este algoritmo como peso de borde.

Al dar salida, digamos la mejor tasa de la solución, la tasa utilizada en la matriz dist [] [] debe multiplicarse por -1 primero y luego elevarse a la potencia bth, donde b es la base (digamos uno de 2, 10 etc.) del registro como se utilizó anteriormente.

Visualizando Floyd-Warshall

Hemos visto el algoritmo DP que Floyd-Warshall implementa para calcular APSP. Visualicemos hasta cierto punto cómo se hace para 4 vértices.

Qué células se utilizan para optimizar

El cálculo se realizará utilizando k = 1 a 4, en el siguiente orden: comenzando con las celdas 1-1, 1-2,. . . . .2-1, 2-2, …… .3-1, ……. 4-3, 4-4.

Al principio, usando k = 1.

Veamos cómo están mejorando los caminos utilizando los siguientes dos ejemplos.

dist [2] [3] = min (dist [2] [3], dist [2] [1] + dist [1] [3])

y dist [3] [4] = min (dist [3] [4], dist [3] [1] + dist [1] [4])

Vemos que para k = 1, todas las rutas se optimizan usando rutas de la 1ra (kth) fila y la 1ra (kth) columna.

Kth Row and Column no cambian

¿Qué pasa con los caminos en la fila k y la columna k?

dist [1] [2] = min (dist [1] [2], dist [1] [1] + dist [1] [2]) – bueno, no tiene sentido actualizar dist [1] [2] añadiéndole algo más.

Entonces vemos, en una cierta iteración kth, la fila kth y la columna kth se usan para actualizar el resto de las rutas mientras ellas mismas no cambian.

En k = 1

En k = 2

En k = 3

En k = 4

Considere que solo se calculó la matriz 3X3

Ahora suponga que no consideramos que teníamos 4 vértices. Más bien consideramos que teníamos 3 vértices y cálculos de APSP completos para todos los caminos en la matriz 3X3. Ignoramos la cuarta fila y la columna por completo.

Entonces tenemos APSP calculado para la siguiente matriz usando k = 1, 2 y 3.

Agregar 4to vértice

Digamos que el 4to vértice llega ahora. Primero, podemos comparar los cálculos utilizados para la matriz 3X3 anterior con los mismos para la matriz 4X4 como se muestra anteriormente y descubrir qué deben hacerse todos los cálculos ahora para extender esta matriz 3X3 a la matriz 4X4 para acomodar el nuevo cuarto vértice.

Encontraremos que al principio tenemos que optimizar la cuarta fila y columna usando k = 1, 2 y 3. Hagamos eso.

Tenga en cuenta que en este punto, la cuarta fila y la columna no se utilizan para optimizar las rutas para la matriz 3X3 anterior. Entonces, ahora que tenemos la cuarta fila y columna optimizadas usando k = 1, 2 y 3, tenemos que optimizar esa matriz 3X3 usando k = 4.

De esta manera, no perdemos ningún cálculo si hubiéramos considerado los 4 vértices de una vez. Y así hemos terminado con la optimización de todas las rutas en la matriz 4X4.

Código

dist [] [] // matriz APSP, ya calculada para vértices n-1

p [] [] // matriz predecesora, ya calculada para vértices n-1

dist [n] [] = ∞

dist [] [n] = ∞

dist [n] [n] = 0

para cada borde (i, n)

dist [i] [n] = peso (i, n)

p [i] [n] = n

para cada borde (n, i)

dist [n] [i] = peso (n, i)

p [n] [i] = i

para k = 1 a n-1

para i = 1 a n-1

si dist [i] [n]> dist [i] [k] + dist [k] [n]

dist [i] [n] = dist [i] [k] + dist [k] [n]

p [i] [n] = p [i] [k]

para j = 1 a n

si dist [n] [j]> dist [n] [k] + dist [k] [j]

dist [n] [j] = dist [n] [k] + dist [k] [j]

p [n] [j] = p [n] [k]

para i = 1 a n-1

para j = 1 a n-1

si dist [i] [j]> dist [i] [n] + dist [n] [j]

dist [i] [j] = dist [i] [n] + dist [n] [j]

p [i] [j] = p [i] [n]

Complejidad

La complejidad de esta construcción incremental para un nuevo vértice es claramente O (n ^ 2). Eso tiene sentido. Después de todo, para n vértices el costo es O (n ^ 3), que es el costo de Floyd-Warshall, si todos los n vértices fueran considerados de una vez.

Pero este edificio incremental hace una gran diferencia. Por ejemplo, considere que tenemos 1000 vértices para los cuales ya hemos calculado APSP usando mil millones de cálculos. Ahora que llega el vértice número 1001, podemos acomodar el nuevo vértice con un costo de 1 millón (aproximadamente) de cálculos en lugar de hacer más de mil millones de cálculos desde cero, algo que puede ser inviable para muchas aplicaciones.

Imprimir ruta de arbitraje

Podemos encontrar el primer ciclo negativo al buscar (para un valor negativo) en las diagonales de la matriz dist [] [], si existe, y luego imprimir la ruta asociada. Para la reconstrucción del camino, podemos seguir los pasos descritos anteriormente.

Esta publicación apareció originalmente como Solución – Algoritmo de arbitraje de divisas en mi blog Sharing Experiences ( gopalcdas dot com ).

Sí, Floyd-Warshall, tres bucles for anidados.

  1. Ejecute el algoritmo Dijkstra N veces.
  2. Ejecute el algoritmo Floyd-Warshall solo una vez.

More Interesting

Según usted, ¿cuáles son los algoritmos de aprendizaje automático más importantes en la actualidad?

¿Cómo son los problemas de programación competitiva? ¿Son problemas que afectan a la sociedad que pueden resolverse mediante algoritmos informáticos? ¿Puede dar un ejemplo?

¿Cuáles son algunas implementaciones reales de algoritmos altamente utilizados o patrones de diseño que ha utilizado en el desarrollo web front-end?

Cómo ordenar datos multivariados

¿Por qué el algoritmo de búsqueda binaria no es adecuado para usar en una tabla con punteros?

Cómo imprimir una cadena usando un puntero

¿Para qué aplicaciones son especialmente adecuados los lenguajes de programación lógica? ¿Cuándo usarías un lenguaje como Prolog? ¿Cuáles son las aplicaciones más exitosas de la programación lógica?

¿Cuál es el menor número de operaciones necesarias para ordenar una matriz de n objetos arbitrarios?

¿Está sesgado el algoritmo de aleatorización del Reproductor de Windows Media?

¿Cuál es el algoritmo de Apache Hadoop?

¿Dónde puedo encontrar un algoritmo de relevancia marginal máxima en Python para la eliminación de redundancia en dos documentos?

¿Usar un tipo de inserción de 50 elementos tendrá el mismo tiempo de ejecución que usar un tipo de inserción de 10 elementos 5 veces?

¿Qué es un filtro de Kalman?

¿El operador 'in' mientras busca claves en Python Dictionary toma O (1)? Si es así, ¿cómo?

¿Cuál es la forma correcta de leer CLRS (Introducción a los algoritmos)?