Cómo encontrar las “rutas” de los caminos más cortos de todos los pares con el algoritmo Floyd-Warshall en C#

Introducción

En la publicación anterior , vimos cómo resolver el problema de la ruta más corta de todos los pares utilizando el algoritmo Floyd-Warshall . También exploramos varias formas de mejorar el rendimiento del algoritmo mediante el uso del paralelismo y la vectorización.

Sin embargo, si piensas en los resultados del algoritmo Floyd-Warshall, te darás cuenta rápidamente del momento interesante: conocemos las distancias (valores de los caminos más cortos) entre los vértices de un gráfico, pero no conocemos las "rutas", es decir, no sabemos qué vértices contribuyen a cada camino más corto y no podemos reconstruir estas "rutas" a partir de los resultados que tenemos.

En este artículo, los invito a que me acompañen y amplíen el algoritmo Floyd-Warshall. Esta vez, nos aseguraremos de poder calcular la distancia y reconstruir la “ruta”.

Un poco de teoría conocida…

Antes de sumergirnos en el código y los puntos de referencia, revisemos una teoría sobre cómo funciona el algoritmo Floyd-Warshall.

A continuación se muestra una descripción textual del algoritmo:

1. Comenzamos representando un grafo ( G ) de tamaño N como una matriz ( W ) de tamaño N x N donde cada celda W[i,j] contiene el peso de una arista desde el vértice i hasta el vértice j (ver Figura 1). En los casos en los que no hay aristas entre vértices, la celda se establece en un valor especial NO_EDGE (mostrado como celdas oscuras en la Figura 1).

   
   

2. A partir de ahora, decimos: W[i,j] contiene una distancia entre los vértices i y j .

   
   

3. A continuación, tomamos un vértice k e iteramos a través de todos los pares de vértices W[i,j] verificando si la distancia i ⭢ k ⭢ j es menor que la distancia actualmente conocida entre i y j .

   
   

4. El valor más pequeño se almacena en W[i,j] y el paso n.° 3 se repite para los siguientes k hasta que todos los vértices de G se hayan utilizado como k .

Aquí está el pseudocódigo:

 algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm

Una vez terminado, cada celda W[i,j] de la matriz W contendrá una distancia de la ruta más corta entre los vértices i y j o un valor NO_EDGE , si no hay una ruta entre ellos.

Como mencioné al principio, tener solo esta información hace que sea imposible reconstruir las rutas entre estos vértices. Entonces… ¿qué deberíamos hacer para poder reconstruir estas rutas?

Bueno… puede que suene obvio pero… ¡necesitamos recopilar más datos!

…Un poco de la misma teoría pero desde un ángulo diferente

La esencia del algoritmo Floyd-Warshall es un compartimento de distancia conocida W[i,j] con una distancia de camino potencialmente nuevo de i a j a través del vértice intermedio k .

Le presto tanta atención a este detalle porque es la clave para preservar la información de la ruta. Tomemos el gráfico anterior de 5 vértices (ver Imagen 2) y ejecutemos el algoritmo Floyd-Warshall en él.

Inicialmente, conocemos todos los bordes del gráfico, lo que nos da las siguientes rutas: 0 ⭢ 1 :2 , 0 ⭢ 4 :10 , 1 ⭢ 3 :1 , 2 ⭢ 4 :1 , 3 ⭢ 2 :1 y 3 ⭢ 4 :3 .

También sabemos que no hay aristas que conduzcan al vértice 0 , por lo que ejecutar un algoritmo para k = 0 no tiene sentido. También es obvio que hay una única arista ( 0 ⭢ 1 ) que conduce desde el vértice 0 al vértice 1 , lo que también hace que la ejecución de todos i != 0 (la i es "desde" aquí) no tenga sentido y, como el vértice 1 tiene aristas con 2 y 4 , tampoco tiene sentido ejecutar algoritmos para ningún j que no sea 2 o 4 (la j es "hasta" aquí).

Es por eso que nuestro primer paso será ejecutar un algoritmo para k = 1 , i = 0 y j = 2,4 .

Hemos encontrado dos caminos: un nuevo camino ( 0 ⭢ 1 ⭢ 2 ) y un atajo ( 0 ⭢ 1 ⭢ 4 ). Ambos pasan por el vértice 1 . Si no almacenamos esta información (el hecho de que llegamos a 2 y 4 a través de 1 ) en algún lugar ahora mismo, se perderá para siempre (y eso es todo lo contrario de lo que queremos).

¿Qué debemos hacer entonces? Actualizaremos la matriz W con los nuevos valores (ver Imagen 3a) y también almacenaremos el valor de k (que es k = 1 ) en las celdas R[0,2] y R[0,4] de una nueva matriz R del mismo tamaño que la matriz W pero inicializada con valores NO_EDGE (ver Imagen 3b).

Por ahora, no te concentres en qué es exactamente la matriz R Sigamos adelante y ejecutemos el algoritmo para el próximo k = 2 .

Aquí, haremos el mismo análisis (para entender qué combinaciones tienen sentido ejecutar) que hicimos para k = 1, pero esta vez, utilizaremos la matriz W en lugar del gráfico G Observa la matriz W , especialmente en la columna n.° 2 y la fila n.° 2 (Imagen 4).

Aquí se puede ver que hay dos caminos al vértice 2 desde el vértice 0 y desde el vértice 1 (columna n.° 2), y dos caminos desde el vértice 2 al vértice 3 y al vértice 4 (fila n.° 2). Sabiendo esto, tiene sentido ejecutar el algoritmo solo para combinaciones de k = 2 , i = 0,1 y j = 3,4 .

Como ya hemos hecho anteriormente, estamos actualizando las celdas W[0,3] , W[0,4] , W[1,3] , W[1,4] con nuevas distancias y las celdas R[0,3] , R[0,4] , R[1,3] y R[1,4] con k = 2 (ver Figura 5).

Sólo queda k = 3 para procesar (porque no hay aristas que conduzcan desde el vértice 4 a ningún otro vértice en el gráfico).

Nuevamente, echemos un vistazo a la matriz W (Imagen 6).

Según la matriz W , hay tres caminos al vértice 3 desde los vértices 0 , 1 y 2 (columna n.° 3), y hay un camino desde el vértice 3 hasta el vértice 4 (fila n.° 3). Por lo tanto, tenemos los siguientes caminos para procesar:

Esta fue la última iteración del algoritmo. Solo falta actualizar las celdas W[0,4] , W[1,4] , W[2,4] con las nuevas distancias y establecer las celdas R[0,4] , R[1,4] , R[2,4] en 3 .

Esto es lo que tenemos al final del algoritmo (Imagen 7).

Como sabemos por la publicación anterior , la matriz W ahora contiene todos los pares de caminos más cortos en el grafo G Pero, ¿qué se almacena dentro de la matriz R ?

Regreso

Cada vez que encontrábamos un nuevo camino más corto, actualizábamos la celda correspondiente de la matriz R con el valor actual de k . Si bien, al principio, esta acción puede parecer misteriosa, tiene un significado muy simple: estábamos almacenando el vértice desde el cual llegamos al vértice de destino: i ⭢ k ⭢ j (aquí llegamos a j directamente desde k ).

Este momento es crucial, porque conocer el vértice del que venimos nos permite reconstruir la ruta moviéndonos hacia atrás (como una langosta) desde el vértice j (el “hacia”) hasta el vértice i (el “desde”).

A continuación se muestra una descripción textual del algoritmo para reconstruir la ruta de i a j :

1. Preparar la matriz dinámica vacía X
2. Comience leyendo un valor z de la celda R[i,j] .
3. Si z es NO_EDGE , entonces se encuentra la ruta de i a j y debemos continuar con el paso n.° 7.
4. Anteponga z a una matriz dinámica X
5. Leer el valor de la celda R[i,z] en z .
6. Repita los pasos 3, 4 y 5 hasta que se alcance la condición de salida en 3.
7. Anteponer i a X.
8. Añade j a X
9. Ahora la matriz dinámica X contiene la ruta de i a j .

En pseudocódigo, parece aún más sencillo:

 algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm

Probémoslo en nuestro gráfico G y reconstruyamos una ruta desde el vértice 0 al vértice 4 (ver Imagen 8).

A continuación se muestra una descripción textual de la ilustración anterior:

1. Comenzamos leyendo el valor de R[0,4] , que da como resultado 3 . Según el algoritmo, esto significa que la ruta va al vértice 4 desde el vértice 3 (mostrado en AZUL).

   
   

2. Como el valor de R[0,4] no es NO_EDGE , procedemos y leemos el valor de R[0,3] que da como resultado 2 (mostrado en VERDE).

   
   

3. Nuevamente, debido a que el valor de R[0,3] no es NO_EDGE , procedemos y leemos el valor de R[0,2] que resulta en 1 (mostrado en ROJO).

   
   

4. Por último, leemos un valor de R[0,1] , que da como resultado el valor NO_EDGE , es decir, no hay más vértices excepto 0 y 4 que contribuyan a la ruta. Por lo tanto, la ruta resultante es: 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 que si observamos el gráfico efectivamente corresponde al camino más corto desde el vértice 0 al vértice 4 .

Un lector atento podría preguntar:

Es una muy buena pregunta. Estamos seguros porque actualizamos la matriz R con un nuevo valor cuando actualizamos el valor de la ruta más corta en la matriz W Por lo tanto, al final, cada fila de la matriz R contiene datos relacionados con las rutas más cortas. Ni más ni menos.

Ahora que hemos terminado con la teoría, es hora de implementarla.

Implementación en C#

En el post anterior , además de implementar una versión original del algoritmo Floyd-Warshall, también integramos varias optimizaciones: soporte para gráficos dispersos, paralelismo y vectorización, y al final también las combinamos todas.

No hay razón para repetir todo esto hoy. Sin embargo, me gustaría mostrarles cómo integrar la memorización de rutas en las versiones originales y vectorizadas (con soporte para gráficos dispersos) del algoritmo.

Integración en el algoritmo original

Puede resultar difícil de creer, pero para integrar la memorización de rutas en la versión original de los algoritmos, todo lo que tenemos que hacer es:

1. Ampliar la firma de la función para incluir la matriz R como un parámetro separado – int[] routes .

   
   

2. Guardar k en routes cada vez que se cambia la ruta más corta (líneas: 2 y 14).

Eso es todo. Sólo una línea y media de código:

 public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Integración en algoritmo vectorizado

La integración en una versión vectorizada (con soporte para gráficos dispersos) requiere un poco más de esfuerzo para completarse, sin embargo, los pasos conceptuales son los mismos:

1. Ampliar la firma de la función para incluir la matriz R como un parámetro separado – int[] routes .

   
   

2. En cada iteración, inicialice un nuevo vector de k valores (línea: 6).

   
   

3. Guardar el vector de valores k en routes cada vez que se cambia la ruta más corta (líneas: 31-32).

   
   

4. Actualice una parte no vectorizada del algoritmo de la misma manera que actualizamos el algoritmo original (línea: 41).

 public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } }

Evaluación comparativa

Recopilar información de rutas parece bastante razonable porque... ¿por qué no? Especialmente cuando es tan fácil de integrar en algoritmos existentes. Sin embargo, veamos qué tan práctico es integrarlo de manera predeterminada.

A continuación se muestran dos conjuntos de pruebas comparativas: con y sin algoritmo (ambos ejecutan versiones originales y vectorizadas del algoritmo). Todas las pruebas comparativas se ejecutaron con BenchmarkDotNet v0.13.1 (.NET 6.0.4 x64) en una máquina equipada con un procesador Intel Core i5-6200U CPU 2.30GHz (Skylake) y con Windows 10.

Todos los experimentos se ejecutaron en el conjunto predefinido de gráficos utilizados en la publicación anterior : 300, 600, 1200, 2400 y 4800 vértices.

A continuación se muestran los resultados de referencia donde los métodos Baseline y BaselineWithRoutes corresponden a la versión original del algoritmo y los métodos SpartialVectorOptimisations y SpartialVectorOptimisationsWithRoutes corresponden a una versión vectorizada (con soporte para gráficos dispersos) del algoritmo.

Los resultados de las pruebas comparativas no son fáciles de interpretar. Si los analizamos con más detenimiento, encontraremos una combinación en la que la recopilación de rutas hizo que el algoritmo se ejecutara más rápido o sin ningún efecto significativo.

Esto parece muy confuso (y si lo es, te recomiendo encarecidamente que escuches este programa con Denis Bakhvalov y Andrey Akinshin para comprender mejor qué cosas complicadas pueden afectar las mediciones). Mi mejor interpretación aquí es que el comportamiento "confuso" es causado por un gran rendimiento de la caché de la CPU (porque los gráficos no son lo suficientemente grandes como para saturar las cachés). En parte, esta teoría se basa en la muestra " negrita ", donde podemos ver una degradación significativa en el gráfico más grande. Sin embargo, no lo verifiqué.

En general, el punto de referencia muestra que si no estamos hablando de escenarios de rendimiento extremadamente alto y gráficos enormes, está bien integrar la memorización de rutas en ambos algoritmos de forma predeterminada (pero tenga en cuenta que duplicará el consumo de memoria porque necesitamos asignar dos matrices W y R en lugar de una).

Lo único que queda es una implementación del algoritmo de reconstrucción de ruta.

Implementación del algoritmo de reconstrucción de ruta

La implementación de algoritmos de reconstrucción de rutas en C# es sencilla y refleja casi por completo el pseudocódigo demostrado anteriormente (usamos LinkedList<T> para representar una matriz dinámica):

 public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; }

El algoritmo anterior no es perfecto y definitivamente se puede mejorar. La mejora más simple que podemos hacer es preasignar una matriz de tamaño sz y completarla en orden inverso:

 public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); }

Si bien esta “optimización” reduce el número de asignaciones a una, no necesariamente hace que el algoritmo sea “más rápido” o “asigne menos memoria” que el anterior. El punto aquí es que si necesitamos tener una ruta ordenada de i a j , siempre tendremos que “invertir” los datos que recuperamos de la matriz R , y no hay forma de escapar de esto.

Pero si podemos presentar datos en orden inverso, entonces podemos utilizar LINQ y evitar asignaciones innecesarias:

 public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; }

Puede haber muchas más variantes de cómo se puede “cambiar” o “mejorar” este código. Lo importante aquí es recordar que cualquier “cambio” tiene desventajas en términos de memoria o ciclos de CPU.

¡Sientete libre de experimentar! ¡Las posibilidades son casi ilimitadas!

Conclusión

En este artículo, profundizamos en la teoría detrás del algoritmo Floyd-Warshall y lo ampliamos con la posibilidad de memorizar las rutas más cortas. Luego, actualizamos las implementaciones de C# (originales y vectorizadas) del artículo anterior . Al final, implementamos algunas versiones del algoritmo para reconstruir las rutas.

Hemos repetido mucho, pero al mismo tiempo espero que hayas encontrado algo nuevo e interesante en este. Este no es el final del problema de los caminos más cortos de todos los pares. Es solo el comienzo.

Espero que hayas disfrutado la lectura ¡y hasta la próxima!