← Volver a los ejercicios

Relajación

Relajar una arista (u, v, w) pregunta si pasar por u mejora lo que se tiene para llegar a v. Si d[u] + w es menor que d[v], baja d[v] y anota a u como predecesor; si no, no toca nada. Diez escenarios, de los directos a los que esconden un infinito, un empate o un peso negativo: hay que decir si algo cambia y con qué valores quedan d[v] y pred[v].

1. El escenario y la respuesta

Escenario .

¿Cambia algo?
d[v] al terminar:

2. Ejecute RELAJAR con estos valores

Paso 0 de 0
Cuando la condición es falsa, las dos líneas de adentro no se ejecutan y sus contadores quedan en cero. Cambie de escenario arriba y la ejecución se recarga con sus valores.

3. Para llevarse

Sin solución aquí. Cambie la comparación de la condición de > a >= y diga en cuáles de los diez escenarios cambia el resultado y qué parte: d[v] o pred[v]. Después explique por qué el cambio que produce en el escenario 3, con d[u] = ∞ es el más dañino para el árbol que forma pred.