Page 160 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 160
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Restando por columna, se tiene:
A la c se resta 1. Por lo tanto, r = 22
1
A la c se resta 3. Por lo tanto, r = 25.
3
De esta forma, c(.) = 25 y la cota superior U = ∞, por lo que la matriz resultante es:
Para S = 2 (1,2)
Ya sabiendo el costo menor, se escoge la primera parte del trayecto, donde A<2,1> = ∞.
En este caso, en toda hilera y en toda columna existe un cero, por lo que r = 0.
Para S = 3 (1,3)
En este caso, toda hilera tiene al menos un cero, pero la primera columna es diferente de cero, por
lo que r = 11.
154
