Network Delay Time

Q: Wie hoch ist die Zeitkomplexität von Network Delay Time?

Mit Dijkstras Algorithmus und einem Binärheap 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. Die Adjazenzliste, die Zeiten und der Heap benötigen O(n + E) Speicherplatz. Bellman-Ford benötigt O(n · E) Zeit und O(n) Speicherplatz.

Q: Warum benötigt Dijkstras Algorithmus nichtnegative Gewichte?

Dijkstra legt den Knoten mit der kleinsten vorläufigen Zeit fest und betrachtet ihn danach nie wieder. Das ist nur dann sicher, wenn kein späterer Weg kürzer sein kann, und bei nichtnegativen Gewichten kostet jeder Weg über einen noch nicht festgelegten Knoten mindestens so viel wie dessen Zeit. Eine negative Kante widerlegt dieses Argument: Ein Weg über einen Knoten, der zunächst teurer erschien, kann am Ende trotzdem günstiger sein. Bei negativen Gewichten verwende Bellman-Ford.

Q: Warum nicht BFS für die Netzwerkverzögerungszeit verwenden?

BFS besucht Knoten in der Reihenfolge, wie viele Verbindungen sie vom Start entfernt sind. Das entspricht der Ankunftszeit nur dann, wenn jede Verbindung gleich lange dauert. Hier unterscheiden sich die Verbindungszeiten, sodass eine Route mit mehr Verbindungen früher ankommen kann. Wären alle Zeiten gleich, würde BFS ausreichen, und bei Zeiten von nur 0 und 1 funktioniert eine deque-basierte 0-1-BFS.

Q: Kannst du Network Delay Time ohne einen Heap lösen?

Ja. Dijkstra mit einem einfachen Array durchsucht alle noch nicht festgelegten Knoten nach der kleinsten Zeit. Das kostet insgesamt O(n²) und erfordert keinen Heap. Das ist bei dichten Graphen die bessere Wahl, bei denen E nahe an n² liegt. Bei dünn besetzten Graphen, wie den großen Tests hier mit 3.000 Knoten und 4.000 Verbindungen, muss die Heap-Version deutlich weniger Arbeit leisten.

MittelKürzeste Wege Graphen Heap

+10

Ein Netzwerk hat n Knoten, die von 1 bis n nummeriert sind. Du erhältst seine Verbindungen als Liste times, wobei times[i] = [u, v, w] bedeutet, dass ein von Knoten u gesendetes Signal Knoten v nach w Zeiteinheiten erreicht. Verbindungen funktionieren nur in eine Richtung.

Ein Signal verlässt Knoten k zum Zeitpunkt 0 und breitet sich über alle erreichbaren Verbindungen aus. Gib den Zeitpunkt zurück, zu dem der letzte Knoten das Signal empfängt, oder -1, falls ein Knoten es nie empfängt.

Funktion

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: die gerichteten Kanten, 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 ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n und u ≠ v
0 ≤ w ≤ 100
Keine zwei Kanten haben sowohl dasselbe u als auch dasselbe v.
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: Knoten 3 empfängt das Signal zum Zeitpunkt 1. Knoten 2 könnte es über seine direkte Verbindung zum Zeitpunkt 4 empfangen, aber über den Weg durch Knoten 3 kommt es bei 1 + 2 = 3 an, und Knoten 4 empfängt es bei 3 + 1 = 4. Knoten 4 ist als Letzter zum Zeitpunkt 4 an der Reihe.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Angenommen, das Signal wird schwächer, nachdem es m Verbindungen überquert hat. Wie findest du unter dieser Begrenzung die Zeit, zu der der letzte Knoten es hört?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jeder Knoten empfängt das Signal nach der Länge seines schnellsten Weges von k. Die Aufgabe besteht also darin, zunächst die kürzesten Wege von einer Quelle in einem gerichteten Graphen zu bestimmen und anschließend das Maximum zu ermitteln. Die Antwort ist die größte kürzeste Zeit oder -1, wenn es zu einem Knoten keinen Weg gibt. Die Übertragungszeiten sind nie negativ. Dadurch kann Dijkstras Algorithmus jeden Knoten mit einem Min-Heap genau einmal und in der Reihenfolge seiner Ankunft festlegen. Unten bezeichnet E die Anzahl der Verbindungen, also times.length.

Tiefensuche, die bei jeder schnelleren Route erneut besucht

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Starte eine Suche am Knoten k mit der Zeit 0 und folge jedem Link, wobei du die bisherige Zeit mitführst. Halte für jeden Knoten die schnellste bisher beobachtete Ankunft fest. Erreicht die Suche einen Knoten nicht früher als den für ihn festgehaltenen Wert, hält sie dort an: Alles, was diese Route weiter hinten erreichen könnte, hat die schnellere Route bereits erreicht. Erreicht sie den Knoten früher, verbessert sich der festgehaltene Wert, und auch alles hinter dem Knoten könnte sich verbessern; daher wird die Suche von dort aus fortgesetzt.

Das ist immer korrekt. Die Suche hält nur dann an, wenn keine Route irgendeinen festgehaltenen Wert verbessert, und die schnellste Route zu jedem Knoten verbessert dessen festgehaltenen Wert irgendwann. Daher entspricht jeder festgehaltene Wert am Ende der tatsächlich schnellsten Zeit.

Das Problem ist, wie oft sich der Wert eines Knotens verbessern kann. Eine Tiefensuche folgt dem ersten Link, auf den sie trifft, bis ganz nach unten. So kann sie einen Knoten zuerst über eine langsame Route erreichen, dann über eine etwas schnellere und anschließend noch einmal über eine schnellere Route. Jedes Mal durchläuft sie auch alles hinter dem Knoten. Stell dir 18 Tore in einer Reihe vor. Zwischen jedem Paar von Toren kannst du entweder einen kostenlosen Link oder einen Umweg nehmen: eine Kette von Links, deren Zeiten zusammen 65.536, 32.768 und so weiter bis hinunter zu 1 ergeben. Wenn sie zuerst die Umwege ausprobiert, erreicht die Suche das letzte Tor zu 131.072 verschiedenen Zeitpunkten, von denen jeder früher ist als der vorherige, und durchläuft jedes Mal die 1.700 Knoten dahinter: etwa 220 Millionen Schritte. Zwei der großen Tests sind auf diese Weise aufgebaut: Bei einem steht jeder Umweg vor dem kostenlosen Link, beim anderen danach. So stolpert die Suche bei einem der Tests, unabhängig davon, in welcher Reihenfolge sie die Links ausprobiert.

Algorithmus

Erstelle eine Adjazenzliste: für jeden Knoten die von ihm ausgehenden Verbindungen mit ihren Zeiten.
Setze die beste Zeit jedes Knotens auf unendlich und lege (k, 0) auf einen Stapel.
Nimm (node, t) vom Stapel. Wenn t nicht kleiner als best[node] ist, überspringe es; andernfalls setze best[node] = t.
Lege für jede Verbindung von node (next, t + w) auf den Stapel, wenn die Ankunftszeit best[next] unterbietet.
Wenn der Stapel leer ist, gib -1 zurück, falls eine beste Zeit noch unendlich ist, andernfalls die größte davon.

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 worst

Bellman-Ford: Entspanne jede Kante bis zu n-1-mal

Idee

Halte für jeden Knoten eine vorläufige Zeit dist fest: 0 für k, unendlich für alle anderen. Eine Kante u → v mit Zeit w zu entspannen bedeutet: Wenn dist[u] + w kleiner als dist[v] ist, bietet die Kante einen schnelleren Weg zu v, also setze dist[v] auf diesen Wert herab. Bellman-Ford durchläuft die gesamte Liste und entspannt in jedem Durchlauf jede Kante.

Warum ergeben sich am Ende die richtigen Zeiten? Betrachte den schnellsten Weg zu einem Knoten, zum Beispiel k → a → b → v. Im ersten Durchlauf wird k → a entspannt, während dist[k] bereits 0 ist, sodass dist[a] danach endgültig feststeht. Im zweiten Durchlauf steht dist[b] endgültig fest, im dritten dist[v]. Ein schnellster Weg muss nie einen Knoten zweimal besuchen, da eine Schleife niemals negative Zeit benötigt. Er hat also höchstens n-1 Kanten, und n-1 Durchläufe legen die Zeiten aller Knoten endgültig fest. Ein Durchlauf, in dem sich nichts ändert, beweist, dass sich auch in keinem späteren Durchlauf etwas ändern kann – dann kannst du aufhören.

Jeder Durchlauf kostet O(E), also beträgt der Aufwand im schlimmsten Fall O(n · E). Die Reihenfolge der Liste entscheidet darüber, wie ungünstig es wird: Sind die Kanten einer langen Route vom entfernten Ende zurück zum Start aufgelistet, wird in jedem Durchlauf ein weiterer Knoten endgültig festgelegt. Ein großer Testfall ist genau so aufgebaut: eine Kette mit 3.000 Knoten, die rückwärts aufgelistet ist. Sie erfordert 2.999 Durchläufe über 4.000 Kanten, also etwa 12 Millionen Entspannungen. Bei dieser Größe läuft das noch schnell genug, aber der Aufwand wächst mit n mal E. Die Stärke von Bellman-Ford liegt woanders: Der Algorithmus bleibt korrekt, wenn die Zeiten einiger Kanten negativ sind – in solchen Fällen versagt Dijkstra.

Algorithmus

Setze dist[k] = 0 und alle anderen dist auf unendlich.
Wiederhole dies bis zu n-1 Mal: für jede Verbindung [u, v, w], falls dist[u] + w < dist[v], setze dist[v] = dist[u] + w.
Beende den Vorgang vorzeitig nach einem Durchlauf, in dem sich nichts ändert.
Gib -1 zurück, falls ein dist noch 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 worst

Dijkstras Algorithmus mit einem Min-Heap

Idee

Bellman-Ford verschwendet Durchläufe, weil der Algorithmus die Verbindungen von Knoten entspannt, deren Zeiten noch nicht endgültig sind, und später zu ihnen zurückkehren muss. Dijkstras Algorithmus entspannt die Verbindungen jedes Knotens genau einmal, sobald dessen Zeit endgültig ist. Die Frage ist, woher man weiß, wann das der Fall ist.

Die Antwort ist eine Greedy-Regel: Von den noch nicht festgelegten Knoten ist derjenige mit der kleinsten vorläufigen Zeit bereits endgültig. Jeder andere Weg zu diesem Knoten muss die festgelegten Knoten irgendwann über einen noch nicht festgelegten Knoten verlassen, dessen Zeit mindestens genauso groß ist; die anschließenden Verbindungen können die Zeit nur erhöhen, da keine negativ ist. Also legt man diesen Knoten fest, entspannt seine Verbindungen und wiederholt den Vorgang. Im ersten Beispiel wird Knoten 1 bei 0 festgelegt und bietet Knoten 2 die Zeit 4 und Knoten 3 die Zeit 1. Knoten 3 ist der kleinste, wird bei 1 festgelegt und senkt die Zeit von Knoten 2 auf 3. Knoten 2 wird bei 3 festgelegt und bietet Knoten 4 die Zeit 4, der zuletzt festgelegt wird. Die Antwort ist 4.

Ein Min-Heap findet die kleinste vorläufige Zeit schnell. Füge (time, node) jedes Mal hinzu, wenn sich die Zeit eines Knotens verbessert, und lasse den älteren Eintrag im Heap, statt nach ihm zu suchen. Wenn der ältere Eintrag später entnommen wird, liegt seine Zeit über der aktuellen Zeit des Knotens, also überspringst du ihn. Jede Verbindung fügt höchstens einen Eintrag hinzu, daher enthält der Heap nie mehr als E + 1 Einträge, und jedes Hinzufügen oder Entnehmen kostet O(log E). Insgesamt ergibt das O(E log E) und für die Adjazenzliste, die Zeiten und den Heap einen Speicherbedarf von O(n + E).

Nicht negative Zeiten machen die Greedy-Regel sicher. Betrachte die Verbindungen A → B mit Zeit 2, A → C mit Zeit 3 und C → B mit Zeit -2. Dijkstra legt B bei 2 fest, doch der Weg über C erreicht ihn bei 1. Ein Signal kann niemals ankommen, bevor es gesendet wird, daher ist jede Zeit hier mindestens 0 und die Regel gilt.

Algorithmus

Erstelle für jeden Knoten eine Adjazenzliste mit (next, w)-Paaren.
Setze dist[k] = 0, alle anderen dist auf unendlich und füge (0, k) in einen Min-Heap ein.
Entnimm das kleinste (t, node). Falls t > dist[node], ist der Eintrag veraltet: Überspringe ihn.
Andernfalls ist t endgültig. Für jede Verbindung von node zu next mit der Zeit w: Falls t + w < dist[next], setze dist[next] = t + w und füge (t + w, next) ein.
Wenn der Heap leer ist, gib -1 zurück, falls ein dist unendlich 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

Die meisten Fehler ignorieren die Richtung der Verbindungen, vertrauen auf den ersten angebotenen Wert für einen Knoten oder verlieren den Überblick über Knoten, die das Signal nie erreicht.

Verbindungen als bidirektional behandeln. [3, 1, 2] überträgt das Signal nur von 3 nach 1. Deshalb erhält Knoten 3 im zweiten Beispiel nie das Signal.
Einfache Breitensuche verwenden. Sie findet die Route mit den wenigsten Verbindungen, nicht die schnellste: Im ersten Beispiel ergibt sie für Knoten 2 die Zeit 4 über die direkte Verbindung statt 3 über Knoten 3.
Einen Knoten als endgültig markieren, wenn er in den Heap eingefügt wird, statt wenn er daraus entnommen wird. Der erste angebotene Wert für einen Knoten ist nicht immer der beste; endgültig ist nur der kleinste aus dem Heap entnommene Eintrag.
Das -1 vergessen. Das Maximum ohne Prüfung zu ermitteln, gibt entweder unendlich zurück oder meldet die größte endliche Zeit und verschweigt den Knoten, der das Signal nie erhalten hat.
Knoten ab 0 zählen. Die Knoten sind von 1 bis n beschriftet. Lege die Arrays also mit der Größe n+1 an und berücksichtige den ungenutzten Index 0 nicht beim Maximum.
Überlauf durch Unendlich. Ist Unendlich der größte int-Wert, läuft dist[u] + w für einen nicht erreichten Knoten u in eine negative Zahl über. Überspringe nicht erreichte Knoten oder verwende einen Wert wie 10^9, der genügend Spielraum lässt.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Network Delay Time?

Mit Dijkstras Algorithmus und einem Binärheap 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. Die Adjazenzliste, die Zeiten und der Heap benötigen O(n + E) Speicherplatz. Bellman-Ford benötigt O(n · E) Zeit und O(n) Speicherplatz.

Warum benötigt Dijkstras Algorithmus nichtnegative Gewichte?

Dijkstra legt den Knoten mit der kleinsten vorläufigen Zeit fest und betrachtet ihn danach nie wieder. Das ist nur dann sicher, wenn kein späterer Weg kürzer sein kann, und bei nichtnegativen Gewichten kostet jeder Weg über einen noch nicht festgelegten Knoten mindestens so viel wie dessen Zeit. Eine negative Kante widerlegt dieses Argument: Ein Weg über einen Knoten, der zunächst teurer erschien, kann am Ende trotzdem günstiger sein. Bei negativen Gewichten verwende Bellman-Ford.

Warum nicht BFS für die Netzwerkverzögerungszeit verwenden?

BFS besucht Knoten in der Reihenfolge, wie viele Verbindungen sie vom Start entfernt sind. Das entspricht der Ankunftszeit nur dann, wenn jede Verbindung gleich lange dauert. Hier unterscheiden sich die Verbindungszeiten, sodass eine Route mit mehr Verbindungen früher ankommen kann. Wären alle Zeiten gleich, würde BFS ausreichen, und bei Zeiten von nur 0 und 1 funktioniert eine deque-basierte 0-1-BFS.

Kannst du Network Delay Time ohne einen Heap lösen?

Ja. Dijkstra mit einem einfachen Array durchsucht alle noch nicht festgelegten Knoten nach der kleinsten Zeit. Das kostet insgesamt O(n²) und erfordert keinen Heap. Das ist bei dichten Graphen die bessere Wahl, bei denen E nahe an n² liegt. Bei dünn besetzten Graphen, wie den großen Tests hier mit 3.000 Knoten und 4.000 Verbindungen, muss die Heap-Version deutlich weniger Arbeit leisten.

Python

def networkDelayTime(times, n, k):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

Erwartet

Network Delay Time

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Tiefensuche, die bei jeder schnelleren Route erneut besucht

Bellman-Ford: Entspanne jede Kante bis zu n-1-mal

Dijkstras Algorithmus mit einem Min-Heap

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben