Encontrar el camino más largo en un árbol de peso no dirigido

Question

Tengo un árbol en el que a cada borde se le asigna un peso (un número real que puede ser positivo o negativo). Necesito un algoritmo para encontrar un camino simple de peso total máximo (es decir, un camino simple donde la suma de los pesos de los bordes en el camino es máxima). No hay ninguna restricción en cuanto a qué nodo comienza o termina el camino.

Tengo un posible algoritmo, pero no estoy seguro de que funcione y estoy buscando una prueba. Aquí la tiene:

1. Seleccione un nodo arbitrario u y ejecutar DFS( u ) para encontrar el camino simple del peso máximo que comienza en u . Dejemos que u , v ) sea este camino.
2. Ejecute el DFS( v ) para encontrar el camino simple del peso máximo que comienza en v . Que este camino sea ( v , z ).

Entonces ( v , z ) es un camino simple de peso máximo. Este algoritmo es lineal en el tamaño del gráfico. ¿Alguien puede decirme si funciona, y si es así, dar una prueba?

Nota: El El problema del camino más largo es NP-Duro para un gráfico general con ciclos. Sin embargo, aquí sólo considero los árboles.

Answer 1

Consideremos el siguiente algoritmo, en el que empezamos por los nodos terminales y los vamos eliminando mientras contabilizamos los caminos correspondientes. Para cada nodo $v$ almacenamos $2$ caminos más largos que hemos obtenido hasta ahora (digamos que de longitud $l_1(v)$ y $l_2(v)$ con $l_1 \geq l_2$ ), que terminan en ese nodo. Inicialmente, todos estos valores se ponen a cero.

1. Dejemos que $v$ un vértice terminal del árbol y que $(u,v)$ sea la arista que la toca.
2. Establecer $l = l_1(v) + w(u,v)$ .
3. Modificar $l_1(u)$ y $l_2(u)$ eligiendo los dos más grandes entre $l_1(u)$ , $l_2(u)$ y $l$ .
4. Eliminar el nodo terminal $v$ y su borde $(u,v)$ del árbol. Si el árbol no está vacío (no hay aristas), vuelva al paso $1$ .

Cuando se han eliminado todas las aristas, podemos demostrar que la longitud máxima del camino viene dada por $\max {(l_1(v) + l_2(v))}$ sobre todos los nodos $v$ en el árbol original. Cada vértice y arista se visita exactamente una vez y todas las operaciones son de tiempo constante, por lo que el algoritmo es lineal en el número de vértices.

He asumido aquí que un camino vacío (camino sin aristas) es admisible y tiene longitud $0$ (por ejemplo, cuando todos los pesos de las aristas son negativos, el camino vacío es el más largo). Pero si sólo quiere caminos no vacíos, podría cambiar la inicialización de $l_1$ y $l_2$ para todos los nodos a $-\infty$ en lugar de $0$ .

Answer 2

Buena idea. De hecho, si todos los pesos de las aristas son 1, esta es una forma estándar de encontrar el diámetro de un árbol. Desafortunadamente, su algoritmo de dos DFS tiene un problema cuando los pesos de las aristas pueden ser negativos.

Consideremos, por ejemplo, el siguiente árbol ponderado por aristas:

Si hacemos un DFS a partir de $u=v_0$ encontramos que hay dos trayectorias máximas de $u$ : a $v_1$ y a $v_3$ , ambos con peso 2. Haciendo la segunda DFS de $v_1$ da lugar a la trayectoria máxima $\langle v_1, v_0, v_2, v_3\rangle$ de peso 4, pero haciendo el DFS de $v_3$ da la trayectoria máxima $\langle v_3, v_2, v_4\rangle$ que tiene un peso de 5.

Estoy bastante seguro de que podrías modificar tu algoritmo para que diera un camino máximo, pero sospecho que la versión modificada ya no sería lineal en el número de vértices. Tengo que pensar en eso.

Answer 3

este algoritmo funciona porque desde que empezamos en cualquier nodo y mientras aplicamos el bfs a ese nodo alcanzamos entre un nodo que es una parte del diámetro. ya que la distancia de ese nodo es máxima sólo para el diámetro por lo que se moverá hacia el final del diámetro. así que el nodo final será uno de los nodos finales del diámetro. y despues de encontrar el extremo podemos aplicar bfs a ese nodo para encontrar el diametro.

pero no soy capaz de entender la lógica detrás de ese algoritmo l1(v) & l2(v). Este algoritmo funciona correctamente pero puede alguien proporcionar la razón detrás de este..

Answer 4

Quiero proponer una forma diferente $\mathcal{O}(n)$ algoritmo. Elegiremos cualquier nodo $u$ e iniciar el dfs desde él. Nuestro $dfs$ devolverá dos cosas.

1. Camino simple más largo con $u$ como el nodo final del camino simple que llamaremos como $V_{1u}$
2. Camino simple más largo del subárbol $u$ que llamamos como $V_{2u}$

Dejemos que $u$ tienen $i$ niños. $u_1, u_2, \dots, u_i$ . Nuestro $dfs(u_j)\ \forall\ 1 \leq j \leq i$ calculará recursivamente la respuesta para $u_1, u_2, \dots, u_i$ . Para cada hijo, obtendremos dos valores como se mencionó anteriormente. Ahora, utilizaremos estos valores para calcular el {par de respuestas} del nodo $u$ utilizando la siguiente forma

1. Camino simple más largo con $u$ como nodo final( $V_{1u}$ ) será $max(w(u, u_j) + V_{1u_j}) \forall 1 \leq j \leq i$ que se calculará en el $\mathcal{O}(i)$ tiempo.
2. Camino simple más largo en $u's$ subárbol( $V_{2u}$ ) será el $max$ de las siguientes cosas :- $max(V_{2u_j})$ , $V_{1u}$ , camino simple más largo con $u$ como uno de sus nodos

Para calcular Camino simple más largo con $u$ como uno de sus nodos (es decir, caminos simples que van entre dos de sus hijos) será simplemente $max(w(u, u_j) + V_{1u_j} + w(u, u_k) + V_{1u_k}) \forall 1 < j < k < i$ . Por lo tanto, tenemos que seleccionar esencialmente máximo y segundo máximo de $w(u, u_j) + V_{1u_j}$ lo que podemos hacer en tiempo lineal(con respecto al tamaño de los hijos de $u$ ). Por lo tanto, podemos devolver ambos valores en un total de $O(n)$ tiempo.