Prog3: Practico 3 Ejercicio 2

Buenas! No supe como utilizar la sugerencia de la parte b) del ejercicio, asi que intenté resolverlo de otra forma.

Quería saber si mi razonamiento es correcto. En particular, no estoy seguro de que haya quedado demostrado que el unico caso en el que hay un camino de largo minimo hasta $w$ es cuando se llega a $w$ y es de nivel $i+1$ .

Gracias y saludos!

Re: Practico 3 Ejercicio 2

de Facundo Benavides - miércoles, 6 de septiembre de 2023, 18:20

hola Nicolás, si subiste una imagen, no se correctamente.
saludos

Re: Practico 3 Ejercicio 2

de Nicolas Aguilera Leal - jueves, 7 de septiembre de 2023, 17:38

Intente subir dos imagenes que son la resolucion del ejercicio. Las dejo como link de drive porque no estoy logrando subirlas al EVA.

https://photos.app.goo.gl/8ZJ2nSzPYsAeqtDu8

https://photos.app.goo.gl/wNqX411idQgJZ17n8

Re: Practico 3 Ejercicio 2

de Facundo Benavides - viernes, 8 de septiembre de 2023, 15:31

hola Nicolás,
la regla de actualización de N no es correcta.
contraejemplo: (1,2) (2,3) (2,4) (3,5) (4,5) (5,6). cuando descubro el nodo 6, según tu regla diría que hay 1 camino de largo mínimo, cuando en realidad hay 2.
notar que:
1- cuando descubro 'v' por primera vez desde un nodo cualquiera, digamos 't1', la cantidad de caminos de largo mínimo desde 'u' hacia 'v' N_v es igual a la cantidad de caminos de largo mínimo desde 'u' hacia 't1' N_t1.
2- la generalización de 1 sería: cuando llego a 'v' desde 'ti' (las subsiguientes veces), sumo a N_v la cantidad de caminos de largo mínimo (alternativos) por los que puedo llegar desde 'u' hacia 'ti' N_ti.
saludos