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].
Escenario .
RELAJAR con estos valoresSin 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.