Práctico 5 ejercicio 3

Práctico 5 ejercicio 3

de Mathias Joaquin Escobar Ferrario -
Número de respuestas: 2

Hola, hice este ejercicio con Dijkstra cambiando la noción de distancia por tiempo. En donde d(u) pasa a ser t(u) y ( d(u) + le ) pasa a hacer fuv(t(u)). t(u) es el tiempo que hay de o a u y fuv(t(u)) es t(u) + el tiempo de viaje de u a v.

La correción es igual que en el libro. En las sugerencias dice que se tienen que tener en cuenta las hipótesis de fuv, la primera la uso para poder hacerlo con Dijkstra, pero la segunda no la estoy usando porque solo evaluo la función en t(u). No se si no estoy viendo una dimensión del problema o falta algo.

En respuesta a Mathias Joaquin Escobar Ferrario

Re: Práctico 5 ejercicio 3

de Fernando Fernandez -
Hola Mathías.
Lo que comentás parece bien encaminado.

La necesidad de la segunda propiedad, que las funciones f_{uv} sean monótonas, complementa la primera, y está relacionado con la restricción de que el algoritmo de Dijkstra valga solo para grafos con aristas de costo no negativo.

En el algoritmo de Dijkstra un vértice u se incluye en el conjunto S cuando ya se conoce la distancia del camino más corto desde s hasta u. Esa distancia no va a cambiar, y, por lo tanto, puede usarse para obtener distancias de caminos que extiendan el camino desde s hasta u hacia otros vértices. Pero si hubiera aristas de costo negativo, por ejemplo, desde V \setminus S hacia S entonces existe la posibilidad de que se encuentren caminos de menor costo hacia u.

Aunque en este problema no hay aristas de costo negativo, si no se cumpliera la segunda propiedad podría ocurrir algo similar. Por ejemplo, y habiendo asumido que t_o=0, si f_{ov}(0) = 1000, y f_{ov}(990) = 995 no podríamos afirmar que t_v = f_{ov}(t_o) es el tiempo a asignarle a t_v. De hecho, no lo sabemos. ¿Podrá ser que f_{ov}(500) sea menor? ¿Habría que probar todos los valores posibles?

¿Esto aclara algo el problema?