Buenos días,
El enunciado es el siguiente:
En esta imagen, 0 es la posici´on de la Estrella de la Muerte y los planetas 1, 2, . . . , 8 son los
planetas que se desea conquistar.
a) Calcula el orden en que deber´ıan conquistarse los planetas para minimizar el coste
financiero de la operaci´on. Ten en cuenta que s´olo se puede abordar la conquista desde
planetas que ya controla el Imperio Gal´actico. Indica qu´e algoritmo utilizas y explica
todos los pasos, as´ı como el coste total de la conquista. Si en alg´un paso del algoritmo
tienes una elecci´on entre dos planetas, elige el que tenga el n´umero de nodo menor.
b) Lord Vader, un comandante del Imperio Gal´actico, puede modificar el coste de la ruta
empleando sus poderes Sith. Esto dividir´ıa por la mitad el coste de las rutas que tienen
un coste par, pero sumar´ıa 2 millones de cr´editos a las rutas con coste impar. Por su
parte, el emperador Palpatine puede rebajar en 1 mill´on de cr´editos el coste de las rutas
con coste impar, pero doblando el coste de las rutas con coste par.
Se pide calcular el nuevo coste total en ambos casos y decidir si es mejor emplear los
poderes de alguno de los dos o no emplear ninguno. Emplea un algoritmo distinto al del
apartado a) y justifica adecuadamente todos los pasos.
El apartado lo he resuelto utilizando el algoritmo de Prim, pero en el segundo apartado se pide que no se utilice el mismo algoritmo
