Ricostruire il Percorso Minimo
Quando si calcola il percorso più breve in un grafo, è possibile anche ricostruirlo al termine dell’elaborazione.
Per farlo, si può memorizzare il “vertice padre” per ogni vertice visitato. In altre parole, se dopo aver elaborato il vertice
v inseriamo il vertice to nella coda, imposteremo nel vettore p che il padre di to è proprio v. Questo ci permetterà di ricostruire l’intero percorso al termine dell’algoritmo. Si può partire dall’ultimo nodo del percorso, poi passare al padre di quest’ultimo, e così via, finché non si arriva a un nodo che non ha alcun padre (il nodo di partenza). Questo si implementa memorizzando un vettore dei padri p aggiuntivo:start = int(input()) # vertice di partenza
d = [-1] * n # distanza dal vertice di partenza
p = [-1] * n # vertice padre
q = deque([start]) # coda di vertici
d[start] = 0 # la distanza dal vertice iniziale a se stesso è 0
while q: # finché la coda non è vuota
v = q.popleft() # estrai il vertice dalla coda
print(v, end=' ') # stampa il vertice
for to in g[v]: # per ogni vertice connesso a v
if d[to] == -1: # se il vertice non è stato visitato
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
p[to] = v # il padre del vertice è v
q.append(to) # aggiungi il vertice alla coda
# Ricostruzione del percorso dal vertice di partenza a quello finale
end = int(input()) # vertice finale
path = [] # percorso dal vertice di partenza a quello finale
while end != -1: # finché esiste un vertice padre
path.append(end) # aggiungi il vertice al percorso
end = p[end] # passa al vertice padre
print(*path[::-1], sep=' -> ') # stampa il percorso in ordine inversoDunque, dopo aver inserito ogni elemento in coda, si memorizza il suo ‘nodo padre’ nell’array
p, e alla fine si ricostruisce il percorso partendo dall’ultimo nodo fino al primo. Alla fine, il percorso viene stampato in ordine inverso, poiché abbiamo elencato i nodi dal fondo del percorso analizzando padre per padre fino all’inizio. Per passare dal nodo di partenza a quello di arrivo, occorre quindi invertire il percorso ottenuto.Facciamo una simulazione dell’algoritmo con diversi input:
n = 4, e = 4
Le coppie
a, b in ingresso sono: [(0, 1), (0, 2), (1, 2), (3, 2)]Il vertice di partenza è 3 e quello finale è 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ aggiungere in coda tutti i vicini non ancora usati
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ aggiungere in coda tutti i vicini non ancora usati
p = [2, 2, 3, -1],q = [0, 1]
v = 0,q = [1]→ aggiungere in coda tutti i vicini non ancora usati
v = 1,q = []→ aggiungere in coda tutti i vicini non ancora usati
- Ricostruisci il percorso
end = 0→end = 2→end = 3
- Stampa
3 → 2 → 0
Attenzione: se alla fine dell’algoritmo
d[end] rimane -1, significa che non è stato possibile raggiungere il vertice end.Sfida: Trovare il Percorso più Breve
Internet è un insieme di computer collegati tra loro, in grado di trasferire dati. In questo caso, i computer sono numerati da 1 a
n e sappiamo quali di questi sono connessi. Alice vuole inviare un messaggio a Bob e il suo obiettivo è farlo arrivare il più velocemente possibile, perciò il percorso deve essere il più breve possibile.Il computer di Alice ha il numero
a, e quello di Bob è b. Bisogna trovare un percorso di computer che trasferisca il messaggio da Alice a Bob nel minor tempo possibile.Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ 100 000) ed e (1 ≤ e ≤ 100 000), che indicano il numero di computer e il numero di connessioni nella rete.La riga successiva contiene due numeri
a e b (1 ≤ a, b ≤ n).Le successive
e righe contengono coppie di interi c1, c2 (1 ≤ c1, c2 ≤ n), che indicano che il computer c1 è connesso al computer c2 e viceversa.Output
Il programma deve stampare il percorso più ottimale che il messaggio può seguire, elencando i numeri dei computer separati da uno spazio. In caso di più percorsi ottimali, è sufficiente stamparne uno qualsiasi.
Esempi
Input | Output |
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