Hola! Estoy viendo la solución alternativa y me surge la duda de por qué en la solución no se contempla el mínimo entre OPT(k-1,v) y el mínimo que plantea la solución. Entiendo que puede existir un camino de a lo sumo k-1 aristas entre v y t.
Esta duda me surgió resolviendo el examen de Julio de 2023, ejercicio 2, porque lo resolví igual que el del parcial pero aquí sí incluyen a OPT(k-1,v). Por qué es esto?
hola Nicolás,
la principal diferencia entre el ejercicio del examen de julio y el del parcial de 2018 es que en examen estas calculando los caminos mas cortos desde un origen hacia cualquier destino y en el parcial debes calcular los caminos mas cortos desde cualquier nodo hacia un destino en particular. Espero poder explicar cómo impacta eso en la diferencia de las soluciones.
en el caso del parcial, los caminos de hasta k pasos incluyen a los caminos de hasta k-1 pasos y como en la recurrencia avanzas un paso hacia el destino, necesariamente el costo de ese paso debe sumarse a el optimo de k-1 pasos, no hay otra forma de llegar al destino. En el caso del examen, la solución se para en todos los nodos adyacentes a un destino y calcula el costo de llegar a esos nodos en a lo sumo k-1 pasos y le suma el costo del paso hasta el destino. sin embargo, podría darse el caso de que se pudiera llegar al destino en a lo sumo k-1 pasos también por lo que hay que quedarse con la mejor de las dos soluciones.
saludos
Javier