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
- ¿Cómo funciona la búsqueda 'YouTube'? ¿Cómo te señala con precisión una canción con solo unas pocas palabras de la letra?
- ¿Cómo afectan los nuevos algoritmos de Instagram a la búsqueda de hashtag?
- ¿Cuál sería la mejor estrategia de negociación algorítmica simple?
- ¿Cuál es el mejor algoritmo de programación que hayas creado?
- ¿Cuáles son algunos problemas en Spoj que usan algoritmos aleatorios?
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:
- Sin usar k : dist [ i ] [ j ] usando nodos intermedios 1 a k -1.
- 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 ).
