Veamos el problema paso a paso.
- Gráfico no dirigido y acíclico
- Si hay más de un componente fuertemente conectado, la distancia máxima para todos los nodos será igual al infinito. Podemos encontrar desde un solo DFS si existen múltiples componentes fuertes o no.
- Supongamos por ahora que el gráfico tiene solo un componente fuertemente conectado. No dirigido, acíclico y uno fuertemente componente => Árbol
- Asumiré que los bordes de los pesos en el árbol son positivos en esta solución.
- Podemos redefinir nuestro problema como Buscar un nodo para el cual la distancia máxima desde cualquiera de los otros nodos sea la más baja en el árbol. En el árbol de abajo podemos observar que los nodos Leaf no pueden ser nuestra respuesta para el árbol con más de dos nodos. Por qué ??
- ¿Podemos resolver este problema SPOJ.com - Problema PT07Z de esta manera?
- ¿Qué tan bien funciona el algoritmo NativeTrack de AppsFlyer?
- ¿Es una buena manera de aprender a resolver el cubo de rubik con algoritmos ya realizados en línea si no tiene idea de cómo resolverlo?
- ¿Por qué se usa el sistema binario?
- ¿Por qué sigo olvidando cómo funciona el algoritmo djikstra?
Supongamos que B es nuestra respuesta. Para cualquier nodo, la distancia desde A será igual o menor que B (pesos positivos). Igual en caso de que el peso del borde AB sea cero. Podemos ver que A también será la respuesta en caso de peso cero. Para cualquier peso, excepto cero para el borde AB, vamos a contradecir nuestra suposición. Por lo tanto, podemos eliminar con seguridad los nodos hoja de nuestro espacio de solución.
Una cosa más que debemos notar es que nuestro nodo de solución tendrá una distancia máxima desde un nodo hoja ya que el gráfico es un árbol.
Aproximación final :-
Retire B y almacene el peso del borde AB en el Nodo A.
Retire F y almacene el peso del borde EF en el Nodo E.
Retire D y almacene el peso del borde del CD en el Nodo C.
Ahora tenemos dos nuevos nodos hoja A y E.
Elimine A y almacene el máximo valor actual en el nodo C y (valor en el nodo A + Peso de CA).
Elimine E también de manera similar y ahora solo tenemos un nodo nuestra respuesta.
Código de sudo: –
Crear matriz
// para almacenar valores de nodo, inicializar con cero
Crear cola LeafNodes
// contiene todos los nodos hoja no eliminados
Solución de nodo;
Mientras que (! Queue.empty ()) {
eliminar el nodo de la hoja superior
Solución = nodo eliminado;
Array [padre] = max (Array [padre], (Array [Solución] + peso del borde de unión)
Agregue el nodo primario a la cola si el primario es el nodo hoja después de eliminar el nodo anterior
}
solución de retorno
No dude en hacer cualquier consulta, gracias
