Una red de enrutadores distinta a la de las diapositivas.
La amplitud guarda desde cuál enrutador se llegó a cada uno, y la ruta se
reconstruye subiendo por esos predecesores. Las flechas azules son los
predecesores; la verde, la ruta al final.
1. La red y la predicción
Las listas de visibles son dirigidas y van en
orden ascendente: 1-2,3, 2-5, 3-4,
4-7, 5-7, 6-1, 7-.
La cuarta consulta usa otra red: 1-2,3, 2-6,
3-7, 6-7.
Consulta:
¿Cuántos saltos tiene la ruta? (−1 si no hay)
2. Ejecute
Cola: vacía
Paso 0 de 0
La condición de la línea 5 detiene la amplitud en
cuanto el destino tiene predecesor.
3. Los predecesores
Enrutador
Se llegó desde
4. Quién queda como predecesor
Cuando varios enrutadores ven a v, ¿cuál queda como su predecesor?
5. Detenerse a tiempo
¿Por qué es correcto detener la amplitud en cuanto el destino tiene predecesor?
La distancia queda fijada al encolar, y la cola
nunca mezcla más de dos capas consecutivas. Una vez el destino tiene
predecesor, ninguna ruta pendiente llega antes.
6. Para llevarse
Sin solución aquí. En la cuarta red, desde el 1 el
vecino de menor número es el 2 y la ruta corta va por el 3. Escriba una
red donde elegir siempre el vecino de menor número lleve a un enrutador
sin salida aunque exista ruta, y explique con las capas por qué la
amplitud no cae en esa trampa.