Emplee el algoritmo visto en clase para calcular las rutas que parten de A y conteste a las siguientes preguntas (para que las preguntas se valoren deben estar debidamente justificadas):
a) ¿En la tabla o cola de prioridad aparece la entrada (H,10) en algún momento? SI / NO (0,25 puntos)
b) ¿En la tabla o cola de prioridad aparece la entrada (D,12) en algún momento? SI / NO (0,25 puntos)
c) ¿El algoritmo inserta en la cola de prioridad (es decir, es alcanzable) antes el nodo F o el nodo C? (0,25 puntos)
d) ¿Cuántas veces cambia el valor de la distancia al nodo H en la tabla teniendo en cuenta que comienza valiendo infinito? (0,25 puntos)
e) ¿Qué nodo sale de la cola de prioridad el 3º? (0,25 puntos)
f) ¿Y el 6º? (0,25 puntos)
g) Dibuja el árbol mínimo de camino mínimo partiendo del router A
Soluciones
🚧
Primero deberemos hacer el algoritmo completo para resolver las preguntas. Se recomiendaseguir el siguiente procedimiento al resolverlo para facilitar encontrar las respuestas a las preguntas planteadas
Dibujar una tabla con las columnas: (Num nodo - Distancia - Visitado - Nodo prev.)
Anotar el desarrollo de la cola de prioridad paso a paso
Proceso
Distancia al nodo inicial =0 , visitado True y nodo previo no aplica (N/A)
Anotamos sus vecinos en la cola de prioridad
En bucle hasta que todos estén visitados o se vacíe la cola
Extraemos el nodo más cercanosin visitar de la cola de prioridad
Anotamos la nueva distancia y el nodo previo (si es mejor) y los marcamos como visitado
Anotamos los vecinos a la cola de prioridad (con la distancia al nodo inicial)
Cola de prioridad (paso a paso)
Paso 0: Estado inicial
A → 0
Paso 1: Desencolamos el nodo A y encolamos sus vecinos no visitados
B → 2
G → 6
Paso 2: Desencolamos el nodo B y encolamos sus vecinos no visitados
E → 4 (2+2)
G → 6
C → 9 (2+7)
Paso 3: Desencolamos el nodo E y encolamos sus vecinos no visitados
G → 6 → 5 (4+1)
F → 6 (4+2)
C → 9
Paso 4: Desencolamos el nodo G y encolamos sus vecinos no visitados
F → 6
C → 9
H → 9 (5+4)
Paso 5: Desencolamos el nodo F y encolamos sus vecinos no visitados
H → 9 → 8 (6+2)
C → 9
Paso 6: Desencolamos el nodo H y encolamos sus vecinos no visitados
C → 9
D → 10 (8+2)
Paso 7: Desencolamos el nodo C y encolamos sus vecinos no visitados
D → 10
Paso 8: Desencolamos el nodo D y encolamos sus vecinos no visitados
Fin del algoritmo
Router
Distancia
Visitado
Prev.
A
∞ → 0
F → V
Inicial
B
∞ → 2
F → V
A
C
∞ → 9
F → V
B
D
∞ → 10
F → V
H
E
∞ → 4
F → V
B
F
∞ → 6
F → V
E
G
∞ → 6 → 5
F → V
A → E
H
∞ → 9 → 8
F → V
G → F
📝
Apartado A
¿En la tabla o cola de prioridad aparece la entrada (H,10) en algún momento?
SI / NO
NO, Ni en la tabla ni en la cola aparece el nodo H con una distancia de 10. Por ello, es imposible llegar a H en exactamente 10 de distancia
📝
Apartado B
¿En la tabla o cola de prioridad aparece la entrada (D,12) en algún momento?
SI / NO
NO, Ni en la tabla ni en la cola aparece el nodo D con una distancia de 12. Por ello, es imposible llegar a H en exactamente 12 de distancia
📝
Apartado C
¿El algoritmo inserta en la cola de prioridad (es decir, es alcanzable) antes el nodo F o el nodo C?
En el paso 2, el nodo C es insertado en la cola de prioridad por primera vez, mientras que no es hasta el paso 3 cuando se inserta el nodo F por primera vez
📝
Apartado D
¿Cuántas veces cambia el valor de la distancia al nodo H en la tabla teniendo en cuenta que comienza valiendo infinito?
Cambia 2 veces: desde infinito a 9 y desde 9 hasta 8
📝
Apartado E
¿Qué nodo sale de la cola de prioridad el 3º?
El nodo E es el tercero en ser desencolado
📝
Apartado F
¿Y el 6º?
El nodo H es el sexto en ser desencolado
📝
Apartado G
Dibuja el árbol mínimo de camino mínimo partiendo del router A
