0Pricing
DSA Interview Prep · Lektion

Network Delay Time und Pfadrekonstruktion

Lösen Sie network-delay-time mit Dijkstra, rekonstruieren Sie mithilfe einer Vorgängerzuordnung den tatsächlichen kürzesten Pfad und erörtern Sie bidirektionales BFS für große Graphen.

Network Delay Time und Pfadrekonstruktion ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Problem Network Delay Time

Network Delay Time (LeetCode 743): Gegeben sind ein Netzwerk mit n Knoten und gerichtete gewichtete Kanten, die die Übertragungszeiten eines Signals darstellen. Finden Sie die minimale Zeit, die ein von Knoten k gesendetes Signal benötigt, um alle Knoten zu erreichen. Wenn ein Knoten nicht erreichbar ist, geben Sie -1 zurück. Dies ist eine direkte Anwendung von Dijkstra: Die Antwort ist die maximale Distanz eines kürzesten Weges von k zu allen Knoten.

Lösung: Dijkstra + Maximum der Distanzen

Führen Sie Dijkstra vom Startknoten k aus, um für alle Knoten v den Wert dist[v] zu ermitteln. Die Antwort ist max(dist.values()). Wenn ein dist[v] weiterhin inf ist, ist dieser Knoten nicht erreichbar – geben Sie -1 zurück. Das Signal durchläuft alle Wege gleichzeitig, daher ist der Engpass der Knoten, dessen Erreichen am längsten dauert.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Pfadrekonstruktion mit dem prev-Array

Um neben den Distanzen auch den tatsächlichen kürzesten Weg zu rekonstruieren, führen Sie ein prev-Dictionary, das für jeden Knoten den besten Vorgänger speichert. Setzen Sie bei jeder Aktualisierung von dist[v] den Wert prev[v] = u. Nach Abschluss von Dijkstra verfolgen Sie vom Zielknoten aus die prev-Zeiger rückwärts, bis Sie den Startknoten erreichen, und kehren die Reihenfolge anschließend um, um den Weg in Vorwärtsrichtung zu erhalten.

import heapq
from collections import defaultdict

def shortest_path_with_reconstruction(times, n, src, dst):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    prev = {i: None for i in range(1, n+1)}
    dist[src] = 0
    heap = [(0, src)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    
    # Reconstruct path from src to dst
    path, node = [], dst
    while node is not None:
        path.append(node)
        node = prev[node]
    return dist[dst], path[::-1]

Bidirektionale BFS für große ungewichtete Graphen

Bei großen ungewichteten Graphen, für die nur ein einziges Start-Ziel-Paar benötigt wird, kann eine bidirektionale BFS deutlich schneller als eine normale BFS sein. Sie führt gleichzeitig eine BFS vom Startknoten und vom Zielknoten aus und stoppt, sobald sich die beiden Suchfronten treffen. Der praktische Geschwindigkeitsgewinn ist erheblich, weil jede Suchfront nur die halbe Graphentiefe durchsuchen muss – dadurch sinkt die Anzahl der besuchten Knoten von O(b^d) auf O(2 × b^(d/2)), wobei b der Verzweigungsfaktor ist.

from collections import deque

def bidir_bfs(graph, src, dst):
    if src == dst: return 0
    
    front_q = deque([src]); front_visited = {src: 0}
    back_q = deque([dst]);  back_visited = {dst: 0}
    
    def expand(queue, visited, other_visited):
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in visited:
                visited[nxt] = visited[node] + 1
                queue.append(nxt)
                if nxt in other_visited:
                    return visited[nxt] + other_visited[nxt]
        return -1
    
    while front_q or back_q:
        res = expand(front_q, front_visited, back_visited)
        if res != -1: return res
        res = expand(back_q, back_visited, front_visited)
        if res != -1: return res
    return -1

Welchen Algorithmus wählen?

Entscheidungshilfe: Ungewichteter Graph, einzelnes Paar → BFS oder bidirektionale BFS. Gewichtet, nicht negative Gewichte, einzelner Startknoten → Dijkstra. Gewichtet, möglicherweise negative Gewichte, einzelner Startknoten → Bellman-Ford. Alle Knotenpaare → Floyd-Warshall (kleines V) oder V × Dijkstra (dünn besetzt). Begrenzte Hops → modifizierter Bellman-Ford mit einer begrenzten Anzahl von Durchläufen. Wenn Sie diese Entscheidungsgrundlage im Interview laut erklären, zeigen Sie algorithmische Reife.

Die Stadt mit den wenigsten erreichbaren Nachbarn finden (LeetCode 1334)

Gegeben sind Städte mit gewichteten Wegen und einem distanceThreshold. Finden Sie die Stadt, die innerhalb dieses Schwellenwerts von den wenigsten anderen Städten erreichbar ist (bei Gleichstand wird der größere Stadtindex bevorzugt). Lösung: Berechnen Sie mit Floyd-Warshall die kürzesten Wege zwischen allen Knotenpaaren und zählen Sie anschließend für jede Stadt, wie viele andere Städte innerhalb des Schwellenwerts erreichbar sind. Geben Sie die Stadt mit der kleinsten Anzahl zurück (bei Gleichstand: der größte Index).

def findTheCity(n, edges, distanceThreshold):
    INF = float('inf')
    dist = [[INF]*n for _ in range(n)]
    for i in range(n): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = dist[v][u] = w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    
    best_city, best_count = -1, n
    for city in range(n):
        count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
        if count <= best_count:
            best_count = count
            best_city = city
    return best_city

print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4))  # 3

Pfad in einem gewichteten DAG

Für einen gerichteten azyklischen Graphen (DAG) lassen sich kürzeste (oder längste) Wege durch topologische Sortierung und Relaxierung in O(V+E) finden – schneller als mit Dijkstra. Verarbeiten Sie die Knoten in topologischer Reihenfolge; wenn Sie den Knoten u verarbeiten, relaxieren Sie alle ausgehenden Kanten. Für längste Wege (nützlich bei der Projektplanung bzw. beim kritischen Pfad) negieren Sie die Gewichte oder ändern Sie min in max.

from collections import deque

def dag_shortest_path(V, edges, source):
    graph = [[] for _ in range(V)]
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    # Topological sort (Kahn's)
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    topo = []
    while queue:
        node = queue.popleft(); topo.append(node)
        for nxt, _ in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0: queue.append(nxt)
    # Relax in topological order
    dist = [float('inf')] * V
    dist[source] = 0
    for u in topo:
        if dist[u] != float('inf'):
            for v, w in graph[u]:
                dist[v] = min(dist[v], dist[u] + w)
    return dist

Kürzester Pfad in einer Matrix mit Hindernissen

Eine häufige Interviewvariante besteht darin, den kürzesten Pfad in einem 2D-Raster von oben links nach unten rechts zu finden, wobei Zellen blockiert sein können. Dies ist ein Problem für ungewichtete BFS (jeder Schritt kostet 1). Verwenden Sie eine BFS mit Bewegung in vier Richtungen und markieren Sie Zellen beim Einreihen als besucht, nicht erst beim Entfernen aus der Warteschlange, damit sie nicht erneut besucht werden. Wenn Hindernisse mit Kosten durchquert werden können, verwenden Sie Dijkstra auf dem 2D-Raster und behandeln Sie es als gewichteten Graphen.

from collections import deque

def shortest_path_binary_matrix(grid):
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    while queue:
        r, c, d = queue.popleft()
        if r == n-1 and c == n-1:
            return d
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
                visited.add((nr,nc))
                queue.append((nr, nc, d+1))
    return -1

print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]]))  # 4

BFS mit mehreren Startknoten

Wenn mehrere Startpunkte existieren (z. B. mehrere „Tore“ in einem Raster oder mehrere Ursprünge in einer Karte), führen Sie eine BFS mit mehreren Startknoten aus: Reihen Sie alle Startknoten gleichzeitig mit der Distanz 0 ein. So wird in einem einzigen BFS-Durchlauf die kürzeste Distanz vom jeweils nächstgelegenen Startknoten zu jeder Zelle berechnet. Diese Technik vermeidet eine separate BFS für jeden Startknoten und hat insgesamt eine Laufzeit von O(V+E).

Zusammenfassung der Algorithmenauswahl

Ein kompakter Entscheidungsbaum: einzelner Startknoten, nicht negative Gewichte → Dijkstra O((V+E) log V). Einzelner Startknoten, negative Gewichte → Bellman-Ford O(VE). Alle Knotenpaare, kleines V → Floyd-Warshall O(V³). DAG, beliebige Gewichte → Topologische Sortierung + Relaxierung O(V+E). Ungewichtet → BFS O(V+E). Pfade in Rastern → BFS (ungewichtet) oder Dijkstra mit Heap (gewichtet). Merken Sie sich diese Tabelle – sie beantwortet Rückfragen in jedem Interview zu kürzesten Wegen.

Pfadfindung in Interviewfragen

In vielen Interviewaufgaben soll der tatsächliche Pfad und nicht nur seine Kosten gefunden werden. Klären Sie immer: Benötigen Sie den Pfad oder nur die Distanz? Wenn der Pfad benötigt wird, legen Sie von Anfang an ein prev-Dictionary an. Häufige Fehler sind, prev[source] = None nicht als Endbedingung zu initialisieren und die Rekonstruktionsreihenfolge zu verwechseln (vom Ziel zum Start zurückverfolgen und anschließend umkehren). Üben Sie die Pfadrekonstruktion zunächst an Beispielen mit 3-4 Knoten, bevor Sie größere Probleme bearbeiten.

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion im Bereich Data Structures & Algorithms — Coding Interview Prep.

Zusammenfassung der Lektion

In dieser Lektion haben Sie gelernt: Network Delay Time wird nach Dijkstra mit max(dist.values()) beantwortet, die Pfadrekonstruktion verwendet ein prev-Array, das bei jeder Verbesserung von dist[v] aktualisiert wird, und eine bidirektionale BFS kann den Suchraum für ungewichtete kürzeste Wege zwischen einem einzelnen Start-Ziel-Paar halbieren. Als Nächstes beschäftigen wir uns mit der Anordnung von Graphen und Kahn-Algorithmus zur topologischen Sortierung.

Häufig gestellte Fragen

Ist die Lektion „Network Delay Time und Pfadrekonstruktion“ kostenlos?

Ja — der vollständige Text von „Network Delay Time und Pfadrekonstruktion“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Network Delay Time und Pfadrekonstruktion“?

Lösen Sie network-delay-time mit Dijkstra, rekonstruieren Sie mithilfe einer Vorgängerzuordnung den tatsächlichen kürzesten Pfad und erörtern Sie bidirektionales BFS für große Graphen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „Network Delay Time und Pfadrekonstruktion“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Dijkstras Algorithmus mit einer Priority Queue
  2. Bellman-Ford und negative Zyklen
  3. Floyd-Warshall: Kürzeste Wege zwischen allen Knotenpaaren
  4. Network Delay Time und Pfadrekonstruktion
← Zurück zu DSA Interview Prep