Tengo un gráfico acíclico dirigido con bordes positivos. Tiene una única fuente y un conjunto de objetivos (vértices más alejados de la fuente). Encuentro los caminos más cortos desde la fuente hasta cada objetivo. Algunos de estos caminos se superponen. Lo que quiero es un árbol de ruta más corta que minimice la suma total de pesos en todos los bordes.Cómo minimizar el costo total del árbol de ruta más corta
Por ejemplo, considere dos de los objetivos. Dado que todos los pesos de los bordes son iguales, si comparten una sola ruta más corta durante la mayor parte de su longitud, entonces es preferible a dos rutas más cortas que no se superponen (menos aristas en el árbol equivalen a un costo global más bajo).
Otro ejemplo: dos caminos no se superponen para una pequeña parte de su longitud, con un alto costo para las rutas no superpuestas, pero de bajo costo para la ruta compartida larga (bajo costo combinado). Por otro lado, dos rutas no se solapan en la mayor parte de su longitud, con bajos costos para las rutas no superpuestas, pero alto costo para la ruta corta compartida (también, bajo costo combinado). Hay muchas combinaciones Quiero encontrar soluciones con el costo total más bajo, dado todos los caminos más cortos desde el origen hasta el objetivo.
En otras palabras, quiero los árboles de ruta más corta y más corta.
¿Suena esto con alguien? ¿Alguien puede indicarme algoritmos relevantes o aplicaciones análogas?
¡Salud!
Hm ... intentar la partición aunque no estoy seguro. los caminos en conjuntos que no tienen nada en común con los demás. Tal vez revertir todos los bordes y resolver el problema del complemento ... –
Simplemente elimine los nodos y bordes que no están en ninguna ruta de la fuente al objetivo y calcule el árbol de expansión de peso mínimo del DAG resultante. Parece que funcionará. Una de las respuestas lo menciona también. –
Parece que esto es NP-Complete y MST no era más que un reclamo. He publicado una respuesta. –