graph - tag - og:type

¿Cómo encontrar la ruta más larga en un gráfico con un conjunto de puntos de inicio y destino?

Question

Tengo un DAG (con costos / pesos por borde) y quiero encontrar la ruta más larga entre dos conjuntos de nodos. Los dos conjuntos de nodos de inicio y destino son desunidos y de tamaño pequeño en comparación con el número total de nodos en el gráfico.

Sé cómo hacer esto de manera eficiente entre un nodo de inicio y uno de destino. Con múltiples, puedo enumerar todas las rutas desde cada inicio hasta cada nodo de destino y elegir la más larga, pero eso requiere un número cuadrático de búsquedas de una sola ruta. ¿Hay alguna manera mejor?

Answer 1

Supongo que desea la ruta más larga posible que comience en cualquiera de los nodos del primer conjunto y finalice en cualquiera de los nodos del segundo conjunto. Luego puedes agregar dos nodos virtuales :

• El primer nodo no tiene predecesores y sus sucesores son los nodos del primer conjunto.

• El segundo nodo no tiene sucesores y sus predecesores son los nodos del segundo conjunto.

Todos los bordes recién agregados deben tener peso cero.

La gráfica aún sería un DAG. Ahora, si usa el algoritmo estándar para encontrar la ruta más larga en el DAG entre los dos nodos nuevos, obtendrá la ruta más larga que comienza en el primer conjunto y termina en el segundo conjunto, excepto que habrá un cero adicional. borde ponderado al principio y un borde extra ponderado en cero al final.

Por cierto, esta solución es esencialmente ejecutar el algoritmo desde todos los nodos del primer conjunto, pero en paralelo a la aproximación secuencial que sugiere su pregunta.