← Volver a los ejercicios

La ruta con menos saltos

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

EnrutadorSe 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.