BFS Kürzeste Pfadlänge
Da der BFS-Algorithmus bei einem Knoten startet und sich allmählich auf dessen Nachbarn ausweitet, kann er verwendet werden, um den kürzesten Pfad vom Startknoten zu allen anderen Knoten im Graphen zu bestimmen. Dafür müssen wir den ursprünglichen Algorithmus geringfügig anpassen. Wir verwenden ein Distanz-Array
d, das anfangs mit -1 gefüllt wird. Falls der Wert eines Knotens -1 ist, bedeutet das, dass dieser Knoten noch nicht besucht wurde. Ist der Wert dagegen positiv, repräsentiert er die Distanz dieses Knotens zum Startknoten:from collections import deque
n, e = map(int, input().split()) # n: Knoten, e: Kanten
g = [[] for _ in range(n)] # Graph - Adjazenzliste
for _ in range(e): # Kanten einlesen
a, b = map(int, input().split()) # a -> b und b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # Startknoten
d = [-1] * n # Distanz vom Startknoten
q = deque([start]) # Warteschlange von Knoten
d[start] = 0 # Distanz vom Startknoten zum Startknoten ist 0
while q: # solange die Warteschlange nicht leer ist
v = q.popleft() # Hole Knoten aus der Warteschlange
print(v, end=' ') # gib den Knoten aus
for to in g[v]: # für jeden Knoten, der mit v verbunden ist
if d[to] == -1: # wenn der Knoten noch nicht besucht wurde
d[to] = d[v] + 1 # (start -> to) = (start -> v) + 1
q.append(to) # füge Knoten zur Warteschlange hinzu
print(d)Zunächst wird das Distanz-Array
d mit -1 initialisiert, was signalisiert, dass keiner der Knoten bisher besucht wurde. Anschließend setzen wir d[start] auf 0, wodurch wir festhalten, dass der Startknoten zu sich selbst die Distanz 0 hat.Sobald der Algorithmus weitere Knoten verarbeitet, werden deren jeweilige Distanzwerte im Array
d aktualisiert. So erhalten wir letztendlich alle Distanzwerte vom Startknoten zu den übrigen Knoten im Graphen.Lass uns den Algorithmus an ein paar Beispielen durchgehen:
n = 4, e = 4
Die Eingabe mit den Paaren
a, b lautet: [(0, 1), (0, 2), (1, 2), (3, 2)]Der Startknoten ist 3
d = [-1, -1, -1, 0],q = [3]
v = 3,q = []→ alle unbenutzten Nachbarn in die Warteschlange einfügen
d = [-1, -1, 1, 0],q = [2]
v = 2,q = []→ alle unbenutzten Nachbarn in die Warteschlange einfügen
d = [2, 2, 1, 0],q = [0, 1]
v = 0,q = [1]→ alle unbenutzten Nachbarn in die Warteschlange einfügen
v = 1,q = []→ alle unbenutzten Nachbarn in die Warteschlange einfügen
- Fertig
n = 5, e = 4
Die Eingabe mit den Paaren
a, b lautet: [(0, 1), (0, 2), (1, 2), (3, 4)]Der Startknoten ist 0
d = [0, -1, -1, -1, -1],q = [0]
v = 0,q = []→ alle unbenutzten Nachbarn in die Warteschlange einfügen
d = [0, 1, 1, -1, -1],q = [1, 2]
v = 1,q = [2]→ alle unbenutzten Nachbarn in die Warteschlange einfügen
v = 2,q = []→ alle unbenutzten Nachbarn in die Warteschlange einfügen
- Fertig
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
Herausforderung: Finde die Kürzeste Pfadlänge
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Deine Aufgabe ist es, den kürzesten Pfad zwischen Knoten 1 und Knoten v zu bestimmen. Falls zwischen den beiden Knoten keine Verbindung existiert, soll das Programm "Impossible" ausgeben.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).Die folgenden
e Zeilen enthalten jeweils zwei ganze Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Diese Angabe bedeutet, dass Knoten v1 mit Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll die Länge des kürzesten Pfades zwischen
1 und v ausgeben.Beispiele
Eingabe | Ausgabe |
5 6
1 2
2 3
1 3
3 4
4 3
3 5 | 2 |
2 1
1 2 | 1 |
2 0 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB