¿Los caminos más cortos entre todos los pares de nodos en árboles?

Question

Esta es una solicitud de referencia, ya que estoy seguro de que lo que sigue no es nuevo, pero no puedo encontrarlo.

Supongamos que tenemos un árbol finito $T$ con pesos no negativos en las aristas. De manera ingenua, calcular las longitudes de los caminos (es decir, la suma de los pesos a lo largo del camino único) entre cada par requiere $O(n^3)$ pasos: hay $\binom{n}{2}$ pares de vértices y siempre podemos acotar el número de aristas en cualquier camino por $n-1$.

Sin embargo, podemos hacerlo mucho mejor con el siguiente truco. Elija una raíz $r$ para $T$ de manera arbitraria. Defina el ancestro común más cercano de $i$ y $j$ como el vértice $a$ donde el camino desde $i$ hasta $r$ se encuentra con el camino desde $j$ hasta $r$. Entonces, si $d(\cdot,\cdot)$ denota la distancia en $T$, obtenemos $d(i,j) = d(i,r) + d(j,r) - 2d(a,r).

Es fácil ver que todos los $d(i,r)$ se pueden calcular en $O(n)$ pasos con BFS. También hay una estructura de datos de Harel y Tarjan que, después de un preprocesamiento de $O(n)$, responderá consultas del ancestro común más cercano en tiempo $O(1)$. Entonces, todo el proceso se convierte en $O(n^2)$.

Answer 1

Simplemente haz un bfs en cada nodo. Cada búsqueda te da un camino más corto de uno-a-todos en el árbol.

En total $n$ veces $O(n)$ = $O(n^2)$.

También puedes hacerlo en $O(n)$, si no te importa que las distancias se almacenen de forma implícita (todavía búsquedas $O(1)$): Crea una estructura de datos LCA, y calcula las distancias desde la raíz hasta cada nodo $d(u)$. Entonces, el camino más corto entre $u$ y $v$ es simplemente $d(u)+d(v)-2d(lca(u,v))$.

Answer 2

Otra variante sería comenzar con un vértice arbitrario y luego actualizar la tabla de los caminos más cortos entre todos los pares cada vez que se descubre un nuevo vértice, es decir, adyacente a alguno de los previamente descubiertos.

Cuando se descubre el vértice $v$ a través de la arista $(u,v)$, las entradas de la fila $u$ y de la columna $v$ de la tabla de distancias $T$ se duplican primero en la fila $v$ y la columna $v$ respectivamente; luego, a cada entrada nuevamente generada distinta de cero en la tabla de distancias se le suma el peso $w(u,v)$ de la arista $(u,v)$ y finalmente la distancia de $u$ a $v$ y de $v$ a $u$ se establecen en $w(u,v)

La complejidad secuencial es $O(n^2)$, pero el algoritmo es mucho más simple y, a diferencia de las otras variantes, este algoritmo también funciona para árboles de crecimiento dinámico, es decir, árboles inicialmente desconocidos y/o árboles sin límite superior en tamaño final.

Ese algoritmo también puede aprovechar la capacidad de computación en paralelo, por ejemplo, de las GPUs; la complejidad sería entonces $O(n)$ bajo la suposición de que hay un número ilimitado de procesadores disponibles.