Network Delay Time
Ein Netzwerk hat n Knoten, die von 1 bis n nummeriert sind. Die Verbindung times[i] = [u, v, w] überträgt ein Signal in dieser Richtung und benötigt dafür w Zeiteinheiten, um von Knoten u zu Knoten v zu gelangen.
Ein Signal verlässt zum Zeitpunkt 0 den Knoten k und läuft über jede Verbindung, die es erreichen kann. Gib den Zeitpunkt zurück, zu dem der letzte Knoten das Signal empfängt, oder -1, wenn ein Knoten es nie empfängt.
Funktion
- timesinteger-2d-array
- die gerichteten Verbindungen, jeweils als [u, v, w]
- ninteger
- die Anzahl der Knoten
- kinteger
- der Knoten, der das Signal sendet
- Gibt zurückinteger
- der Zeitpunkt, zu dem der letzte Knoten das Signal empfängt, oder -1
Einschränkungen
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nundu ≠ v0 ≤ w ≤ 100- Keine zwei Kanten haben dasselbe
uund dasselbev. 1 ≤ k ≤ n
Beispiele
- Eingabe
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Ausgabe
- 4
- Erklärung
- Die direkte Verbindung erreicht Knoten 2 zum Zeitpunkt 4, aber der Weg über Knoten 3 kommt bei 1 + 2 = 3 an. Knoten 4 empfängt das Signal zuletzt, bei 3 + 1 = 4.
- Eingabe
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Ausgabe
- -1
- Erklärung
- Knoten 2 hört das Signal zum Zeitpunkt 3, aber die einzige Verbindung zu Knoten 3 verläuft von 3 nach 1. Knoten 3 hört es nie, daher lautet die Antwort -1.
- Eingabe
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Ausgabe
- 2
- Erklärung
- Die Verbindung zu Knoten 3 dauert 0, daher empfängt Knoten 3 das Signal zum Zeitpunkt 0. Knoten 1 empfängt es dann bei 0 + 2 = 2, früher als bei 5 über seine direkte Verbindung.
Weiterführende Frage
Angenommen, das Signal wird nach dem Überqueren von m Verbindungen schwächer. Wie findest du die Zeit, zu der der letzte Knoten es unter dieser Grenze hört?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Ein Knoten empfängt das Signal nach der Dauer der schnellsten Route von
kzu ihm. Die Antwort ist also die größte dieser schnellsten Zeiten oder -1, wenn es zu einem Knoten überhaupt keine Route gibt.Keine Verbindung benötigt negative Zeit. Daher kann der Knoten mit der kleinsten vorläufigen Zeit unter den Knoten, deren Zeit noch nicht endgültig ist, nicht schneller erreicht werden: Jeder andere Weg zu ihm führt durch einen anderen dieser Knoten, der nicht früher erreicht wird. Bestimme die Knoten in der Reihenfolge ihrer Ankunft endgültig.
Halte einen Min-Heap aus
(time, node)-Paaren bereit. Entferne das kleinste Element, überspringe es, wenn der Knoten bereits eine kleinere Zeit hat, und füge jeden Nachbarn hinzu, dessen Zeit sich verbessert. Wenn der Heap leer ist, nimm die größte Zeit.
Lösung
Jeder Knoten empfängt das Signal nach der Länge seines schnellsten Weges von k. Gesucht sind also die kürzesten Wege von einer Quelle, gefolgt von einem Maximum, oder -1, wenn ein Knoten nicht erreichbar ist. Die Übertragungszeiten sind nie negativ, daher legt Dijkstras Algorithmus jeden Knoten nur einmal endgültig fest. Im Folgenden ist E gleich times.length.
Tiefensuche, die bei jedem schnelleren Weg erneut besucht
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Suche von k aus tiefenorientiert, führe dabei die bisherige Zeit mit und halte für jeden Knoten seine schnellste Ankunftszeit fest. Eine Route, die einen Knoten nicht früher als seine bisherige Bestzeit erreicht, wird beendet; eine frühere Ankunft verbessert den Eintrag und die Suche wird fortgesetzt. Jeder Eintrag endet bei der tatsächlich schnellsten Zeit, denn die schnellste Route verbessert ihn irgendwann.
Ein Knoten kann viele Male verbessert werden. Lege 18 Tore in einer Reihe an, wobei jedes benachbarte Paar durch eine kostenlose Verbindung und durch einen Umweg mit Kosten von 65,536, 32,768 und so weiter bis hin zu 1 verbunden ist. Werden zuerst die Umwege ausprobiert, erreicht die Suche das letzte Tor zu 131,072 verschiedenen Zeiten und durchläuft jedes Mal alles dahinter: Der Aufwand ist exponentiell in n.
Algorithmus
- Setze alle besten Zeiten auf unendlich und lege
(k, 0)auf einen Stapel. - Nimm
(node, t)vom Stapel. Überspringe es, sofern nichtt < best[node]gilt; setze dannbest[node] = t. - Lege für jede Verbindung von
node, deren Ankunftbest[next]unterbietet,(next, t + w)auf den Stapel. - Wenn der Stapel leer ist, gib -1 zurück, falls eine der besten Zeiten unendlich ist, andernfalls den größten Wert.
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
best = [INF] * (n + 1) # the fastest arrival found so far at each node
stack = [(k, 0)]
while stack:
node, t = stack.pop()
# A route that is not faster than one already found adds nothing.
if t >= best[node]:
continue
best[node] = t
# Push in reverse so the first listed edge is explored first.
for nxt, w in reversed(graph[node]):
if t + w < best[nxt]:
stack.append((nxt, t + w))
worst = 0
for node in range(1, n + 1):
if best[node] == INF:
return -1
worst = max(worst, best[node])
return worstBellman-Ford: Entspanne jede Kante bis zu n-1-mal
Idee
Speichere für jeden Knoten eine vorläufige Zeit dist, für k den Wert 0. Beim Relaxieren einer Verbindung u → v wird dist[v] auf dist[u] + w gesetzt, wenn dieser Wert kleiner ist. Bellman-Ford relaxiert in jedem Durchlauf jede Verbindung.
Betrachte den schnellsten Weg zu einem Knoten, zum Beispiel k → a → b → v. Im ersten Durchlauf wird dist[a] endgültig festgelegt, im zweiten dist[b], im dritten dist[v]. Ein schnellster Weg wiederholt nie einen Knoten, hat also höchstens n-1 Verbindungen, und n-1 Durchläufe legen die Werte für alle Knoten endgültig fest.
Jeder Durchlauf kostet O(E). Eine Kette mit 3,000 Knoten, die vom anderen Ende aus rückwärts aufgelistet ist, erfordert 2,999 Durchläufe über 4,000 Verbindungen: etwa 12 Millionen Relaxierungen.
Algorithmus
- Setze
dist[k] = 0und alle anderendistauf unendlich. - Wiederhole bis zu n-1-mal: Gehe für jede Verbindung
[u, v, w]wie folgt vor: Wenndist[u] + w < dist[v]gilt, setzedist[v] = dist[u] + w. - Beende den Vorgang vorzeitig, wenn sich bei einem Durchlauf nichts ändert.
- Gib -1 zurück, wenn ein
distnoch unendlich ist, andernfalls den größten Wert.
def networkDelayTime(times, n, k):
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
# A fastest route visits each node at most once, so it has at most n-1 edges,
# and n-1 passes over every edge are enough to find it.
for _ in range(n - 1):
changed = False
for u, v, w in times:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # a pass that improves nothing means every time is final
break
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worstDijkstras Algorithmus mit einem Min-Heap
Idee
Unter den noch nicht festgelegten Knoten ist derjenige mit der kleinsten vorläufigen Zeit bereits endgültig. Jeder andere Weg zu ihm muss die festgelegten Knoten über einen noch nicht festgelegten Knoten verlassen, dessen Zeit mindestens ebenso groß ist, und die danach folgenden Verbindungen addieren nur Zeit, da keine davon negativ ist. Also legst du diesen Knoten fest, lockerst seine Verbindungen einmal und wiederholst den Vorgang.
Ein Min-Heap findet die kleinste Zeit. Wenn sich ein Knoten verbessert, fügst du einen neuen Eintrag hinzu und lässt den alten an Ort und Stelle; ein entnommener Eintrag, dessen Zeit über dist liegt, ist veraltet und wird daher übersprungen. Jede Verbindung fügt höchstens einen Eintrag hinzu, sodass der Heap höchstens E + 1 Einträge enthält und die Gesamtlaufzeit O(E log E) beträgt.
Algorithmus
- Setze
dist[k] = 0, jedes anderedistauf unendlich und füge(0, k)in einen Min-Heap ein. - Entnimm das kleinste
(t, node); wennt > dist[node], überspringe es, da es veraltet ist. - Für jede Verbindung
node → nextmit der Zeitw: Wennt + w < dist[next], setzedist[next] = t + wund füge(t + w, next)ein. - Wenn der Heap leer ist, gib -1 zurück, falls irgendein
distunendlich ist, andernfalls den größten Wert.
import heapq
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
heap = [(0, k)] # (arrival time, node), smallest time on top
while heap:
t, node = heapq.heappop(heap)
# A stale entry: this node was already reached sooner.
if t > dist[node]:
continue
# t is now final: every other route reaches node later.
for nxt, w in graph[node]:
if t + w < dist[nxt]:
dist[nxt] = t + w
heapq.heappush(heap, (t + w, nxt))
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worst
Stolperfallen und Grenzfälle
- Links als bidirektional behandeln.
[3, 1, 2]überträgt das Signal nur von 3 nach 1, daher empfängt Knoten 3 es im zweiten Beispiel nie. - Einfache Breitensuche verwenden. Sie findet den Weg mit den wenigsten Verbindungen: Im ersten Beispiel ergibt sie für Knoten 2 die Zeit 4 statt 3.
- Das -1 vergessen. Das Maximum ohne Prüfung zu nehmen, gibt unendlich zurück oder verbirgt den Knoten, der das Signal nie empfangen hat.
- Den größten int-Wert als Unendlich verwenden.
dist[u] + wläuft dann für einen nicht erreichtenuzu einer negativen Zahl über; überspringe nicht erreichte Knoten oder verwende 10^9.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität von Network Delay Time?
Mit Dijkstras Algorithmus und einem binären Heap beträgt die Laufzeit O(E log E), wobei E die Anzahl der Verbindungen ist. Das entspricht O(E log n), da E höchstens n² beträgt. Der Speicherbedarf beträgt O(n + E). Bellman-Ford benötigt O(n · E) Zeit.
Warum benötigt der Dijkstra-Algorithmus nichtnegative Gewichte?
Dijkstra besucht einen bereits festgelegten Knoten nie erneut. Das ist nur dann sicher, wenn keine spätere Route kürzer sein kann. Bei Verbindungen A → B mit einer Dauer von 2, A → C mit einer Dauer von 3 und C → B mit einer Dauer von -2 legt der Algorithmus B mit einer Dauer von 2 fest, doch über C erreicht die Route den Knoten in 1. Bellman-Ford kann mit negativen Dauern umgehen.
Kannst du das Problem „Network Delay Time“ ohne einen Heap lösen?
Ja. Dijkstra mit einem einfachen Array durchsucht alle noch nicht festgelegten Knoten nach der kleinsten Zeit, was insgesamt O(n²) kostet. Bei dichten Graphen, in denen E nahe bei n² liegt, ist diese Variante im Vorteil. Bei dünn besetzten Graphen, etwa mit 3.000 Knoten und 4.000 Kanten, muss die Heap-Variante deutlich weniger Arbeit leisten.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def networkDelayTime(times, n, k):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Erwartete Ausgabe
4