Tengo un árbol (en el sentido de la teoría de grafos), como el siguiente ejemplo:
Este es un árbol dirigido con un nodo inicial (la raíz) y muchos nodos finales (las hojas). Cada uno de los bordes tiene una longitud asignada.
Mi pregunta es, ¿cómo encontrar el camino más largo que comienza en la raíz y termina en cualquiera de las hojas? El enfoque de fuerza bruta es verificar todos los caminos de la raíz y tomar el que tenga la longitud máxima, pero preferiría un algoritmo más eficiente si lo hubiera.
algorithms
graphs
Graviton
fuente
fuente
Respuestas:
Ran G. dio pistas sobre un algoritmo eficiente, aunque tal vez omitió algunos detalles. Calcular todas las rutas raíz-hoja es, de hecho, un poco ineficiente si está haciendo un trabajo una y otra vez, por ejemplo, si calcula cada ruta y luego calcula la longitud.
Realice el siguiente algoritmo recursivo comenzando con
LongestPath(root)
le dará lo que desea. Esencialmente, calcula recursivamente la ruta más larga para cada subárbol. En cada nodo esto requiere construir los nuevos caminos y devolver el más largo.Esta es una combinación de pseudocódigo con alguna notación de Haskell, por lo que espero que sea comprensible.
fuente