Kürzesten Pfad rekonstruieren
Wenn man den kürzesten Pfad in einem Graphen berechnet, kann man diesen am Ende auch rekonstruieren.
Dazu können wir für jeden besuchten Knoten einen „Elternknoten“ speichern. Das bedeutet, wenn wir den Knoten
to nach der Verarbeitung von v in die Warteschlange einfügen, markieren wir v als Elternknoten von to. So lässt sich der gesamte Pfad am Ende rekonstruieren. Wir beginnen beim letzten Knoten im Pfad und gehen dann jeweils zu dessen Elternknoten. Dieser Vorgang wird so lange fortgesetzt, bis wir einen Knoten erreichen, der keinen Elternknoten hat – das ist unser Startknoten. Das Ganze lässt sich umsetzen, indem wir ein zusätzliches Parent-Array p benutzen:start = int(input()) # Startknoten
d = [-1] * n # Abstand zum Startknoten
p = [-1] * n # Elternknoten
q = deque([start]) # Warteschlange von Knoten
d[start] = 0 # Abstand vom Start zum Start ist 0
while q: # Solange die Warteschlange nicht leer ist
v = q.popleft() # Hole Knoten aus der Warteschlange
print(v, end=' ') # Knoten ausgeben
for to in g[v]: # Für jeden mit v verbundenen Knoten
if d[to] == -1: # Wenn Knoten noch nicht besucht wurde
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
p[to] = v # Elternknoten ist v
q.append(to) # Knoten zur Warteschlange hinzufügen
# Rekonstruktion des Pfads vom Start zum Ende
end = int(input()) # Endknoten
path = [] # Pfad vom Start zum Ende
while end != -1: # Solange ein Elternknoten existiert
path.append(end) # Knoten zum Pfad hinzufügen
end = p[end] # Zum Elternknoten wechseln
print(*path[::-1], sep=' -> ') # Pfad in umgekehrter Reihenfolge ausgebenDadurch, dass wir für jeden neu hinzugefügten Knoten dessen Elternknoten in
p speichern, können wir den Pfad am Ende rekonstruieren, indem wir vom letzten Knoten zurück zum ersten gehen. Am Schluss sollte dieser Pfad in umgekehrter Reihenfolge ausgegeben werden, da wir die Knoten vom Ende her betrachten, bis wir den Startknoten erreichen. Um also vom Start zum Ende zu gelangen, kehren wir den Pfad am Ende um.Lass uns den Algorithmus an einigen Beispielen durchspielen:
n = 4, e = 4
Die Eingaben
a, b lauten: [(0, 1), (0, 2), (1, 2), (3, 2)]Der Startknoten ist 3 und der Endknoten ist 0
p = [-1, -1, -1, -1],q = [3]
v = 3,q = []→ alle noch unbenutzten Nachbarn in die Warteschlange einfügen
p = [-1, -1, 3, -1],q = [2]
v = 2,q = []→ alle noch unbenutzten Nachbarn in die Warteschlange einfügen
p = [2, 2, 3, -1],q = [0, 1]
v = 0,q = [1]→ alle noch unbenutzten Nachbarn in die Warteschlange einfügen
v = 1,q = []→ alle noch unbenutzten Nachbarn in die Warteschlange einfügen
- Rekonstruktion des Pfads
end = 0→end = 2→end = 3
- Ausgabe:
3 → 2 → 0
Beachte, dass, wenn
d[end] am Ende des Algorithmus immer noch -1 ist, der Zielknoten (end) nicht erreicht werden konnte.Herausforderung: Finde die kürzeste Route
Das Internet besteht aus einer Ansammlung von Computern, die untereinander verbunden sind und Daten übertragen können. In diesem Fall sind die Computer mit den Nummern 1 bis
n durchnummeriert, und wir wissen, welche Computer miteinander verbunden sind. Alice möchte eine Nachricht an Bob senden und möchte, dass diese so schnell wie möglich zugestellt wird. Die Route sollte also so kurz wie möglich sein.Alice hat einen Computer mit der Nummer
a, und Bobs Computer hat die Nummer b. Deine Aufgabe ist es, eine optimale Folge von Computern zu finden, die die Nachricht von Alice zu Bob so schnell wie möglich transportiert.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ 100 000) und e (1 ≤ e ≤ 100 000) – die Anzahl der Computer und die Anzahl der Verbindungen im Netzwerk.Die nächste Zeile enthält zwei Zahlen
a und b (1 ≤ a, b ≤ n).Die folgenden
e Zeilen enthalten Paare von ganzen Zahlen c1, c2 (1 ≤ c1, c2 ≤ n). Dieser Eintrag bedeutet, dass der Computer c1 mit dem Computer c2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll die optimalste Route für die Nachricht ausgeben, wobei jede Computernummer durch ein Leerzeichen getrennt wird. Wenn es mehrere gleichwertige optimale Routen gibt, kann eine beliebige davon ausgegeben werden.
Beispiele
Eingabe | Ausgabe |
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