Reconstruir o Caminho Mais Curto
Quando calculamos o caminho mais curto num grafo, também é possível reconstruí-lo no final.
Para isso, podemos guardar o vértice “pai” de cada vértice que visitamos. Isto significa que, se adicionarmos o vértice
to à fila depois de processarmos o vértice v, podemos marcar que o vértice “pai” de to foi v. Isto permite reconstruir todo o caminho no final. Podemos começar a partir do último nó do percurso e, em seguida, avançar para o seu pai. Depois avançamos para o pai do nó atual e continuamos assim até chegarmos a um nó que não tenha pai, que será o nó de partida. Isto pode ser implementado guardando um array de pais adicional, p:start = int(input()) # vértice de partida
d = [-1] * n # distância a partir do vértice de partida
p = [-1] * n # vértice pai
q = deque([start]) # fila de vértices
d[start] = 0 # a distância do vértice de partida para si próprio é 0
while q: # enquanto a fila não estiver vazia
v = q.popleft() # obter vértice da fila
print(v, end=' ') # imprimir vértice
for to in g[v]: # para cada vértice ligado a v
if d[to] == -1: # se o vértice ainda não foi visitado
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
p[to] = v # o pai do vértice é v
q.append(to) # adicionar vértice à fila
# Reconstrução do caminho de start até end
end = int(input()) # vértice de destino
path = [] # caminho de start até end
while end != -1: # enquanto existir um vértice pai
path.append(end) # adicionar vértice ao caminho
end = p[end] # ir para o vértice pai
print(*path[::-1], sep=' -> ') # imprimir o caminho na ordem inversaAssim, depois de adicionarmos cada elemento à fila, marcamos o seu nó pai no array
p e, no final, reconstruímos o itinerário indo do último nó até ao primeiro. No final, o caminho deverá ser impresso na ordem inversa, pois fomos acrescentando elementos a partir do fim do percurso e analisando cada nó-pai até chegar ao início. Portanto, para percorrer do primeiro nó até ao último, é necessário inverter o trajeto que reunimos.Vamos simular o algoritmo em vários conjuntos de dados:
n = 4, e = 4
As entradas de pares
a, b são as seguintes: [(0, 1), (0, 2), (1, 2), (3, 2)]O vértice inicial é 3 e o vértice final é 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ adicionar todos os vizinhos que não foram usados à fila
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ adicionar todos os vizinhos que não foram usados à fila
p = [2, 2, 3, -1],q = [0, 1]
v = 0,q = [1]→ adicionar todos os vizinhos que não foram usados à fila
v = 1,q = []→ adicionar todos os vizinhos que não foram usados à fila
- Reconstruir o caminho
end = 0→end = 2→end = 3
- imprimir
3 → 2 → 0
Note que se
d[end] continuar -1 no final do algoritmo, então não foi possível chegar ao vértice end.Desafio: Encontrar a Rota Mais Curta
A Internet é um conjunto de computadores que estão conectados entre si e podem transferir dados. Neste caso, esses computadores estão numerados de 1 a
n e sabemos que computadores estão ligados entre si. A Alice quer enviar uma mensagem para o Bob e pretende que essa mensagem seja entregue o mais rapidamente possível, o que implica que a rota seja a mais curta possível.A Alice tem um computador com o número
a, e o computador do Bob tem o número b. O seu objetivo é encontrar uma rota ótima de transmissão de dados entre esses dois computadores.Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ 100 000) e e (1 ≤ e ≤ 100 000), que representam o número de computadores e o número de conexões na rede.A linha seguinte contém dois números
a e b (1 ≤ a, b ≤ n).As seguintes
e linhas contêm pares de inteiros c1, c2 (1 ≤ c1, c2 ≤ n), indicando que o computador c1 está ligado ao computador c2 e vice-versa.Saída
O programa deve imprimir a rota mais eficiente para a mensagem, onde cada número de computador é separado por um espaço. No caso de existirem várias rotas igualmente ótimas, pode ser impressa qualquer uma delas.
Exemplos
Entrada | Saída |
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