Reconstruir el camino más corto
Cuando calculamos el camino más corto en un grafo, también es posible reconstruirlo al final.
Para lograrlo, podemos ir guardando el vértice “padre” de cada vértice visitado. Esto significa que, si añadimos el vértice
to a la cola después de procesar el vértice v, marcamos que el vértice padre de to es v. Al terminar, podremos reconstruir todo el camino. Empezamos desde el último nodo del camino y avanzamos hacia su padre. Luego al padre del nodo actual, y así sucesivamente hasta llegar a un nodo que no tenga padre, que será el nodo inicial. Esto puede implementarse guardando un arreglo adicional de padres p:start = int(input()) # vértice de inicio
d = [-1] * n # distancia desde el vértice de inicio
p = [-1] * n # vértice padre
q = deque([start]) # cola de vértices
d[start] = 0 # la distancia desde start hasta start es 0
while q: # mientras la cola no esté vacía
v = q.popleft() # obtener vértice de la cola
print(v, end=' ') # imprimir vértice
for to in g[v]: # para cada vértice conectado con v
if d[to] == -1: # si el vértice no ha sido visitado
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
p[to] = v # el padre del vértice es v
q.append(to) # agregar vértice a la cola
# Reconstrucción del camino desde start hasta end
end = int(input()) # vértice final
path = [] # camino desde start hasta end
while end != -1: # mientras exista un vértice padre
path.append(end) # agregar vértice al camino
end = p[end] # ir al vértice padre
print(*path[::-1], sep=' -> ') # imprimir el camino en orden inversoAsí, luego de añadir cada elemento a la cola, registramos su vértice padre en el arreglo
p y, al finalizar, reconstruimos el camino y lo invertimos, porque fuimos añadiendo los nodos desde el final hasta el comienzo.Al simular este algoritmo con distintos valores de entrada, podemos seguir el proceso paso a paso:
n = 4, e = 4
Los pares de entrada
a, b son: [(0, 1), (0, 2), (1, 2), (3, 2)]El vértice inicial es 3 y el vértice final es 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ añadir todos los vecinos que no hayan sido usados a la cola
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ añadir todos los vecinos que no hayan sido usados a la cola
p = [2, 2, 3, -1],q = [0, 1]
v = 0,q = [1]→ añadir todos los vecinos que no hayan sido usados a la cola
v = 1,q = []→ añadir todos los vecinos que no hayan sido usados a la cola
- Reconstruir el camino
end = 0→end = 2→end = 3
- imprimir
3 → 2 → 0
Observa que, si al finalizar el algoritmo
d[end] sigue siendo -1, significa que no pudimos alcanzar el vértice end.Desafío: Encontrar la ruta más corta
Internet está compuesta por computadoras que están conectadas entre sí y pueden transferir datos. En este caso, dichas computadoras están numeradas de 1 a
n y sabemos cuáles computadoras están conectadas. Alice quiere mandar un mensaje a Bob de la forma más rápida posible. Por lo tanto, la ruta debe ser la más corta posible.La computadora de Alice es la número
a, mientras que la de Bob es b. Se te pide encontrar una ruta óptima de computadoras que transfiera el mensaje desde la de Alice hasta la de Bob lo más rápido posible.Entrada
La primera línea de la entrada contiene dos enteros
n (1 ≤ n ≤ 100 000) y e (1 ≤ e ≤ 100 000), que representan el número de computadoras y el número de conexiones en la red.La siguiente línea contiene dos números
a y b (1 ≤ a, b ≤ n).Las siguientes
e líneas contienen pares de enteros c1, c2 (1 ≤ c1, c2 ≤ n), lo cual indica que la computadora c1 está conectada con la computadora c2, y viceversa.Salida
El programa debe imprimir la ruta más óptima para transferir el mensaje, donde cada número de computadora esté separado por un espacio. Si existen varias rutas óptimas, se puede imprimir cualquiera de ellas.
Ejemplos
Entrada | Salida |
5 5
1 5
1 2
2 3
1 3
3 4
3 5 | 1 3 5 |
5 6
1 5
1 2
2 3
2 4
3 4
4 5
3 5 | 1 2 4 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB