Forberedelse til kodeintervjuer · leksjon

Network Delay Time og rekonstruksjon av stier

Løs «network-delay-time» med Dijkstra, rekonstruer den faktiske korteste stien ved hjelp av et forgjengerkart, og se på toveis BFS for store grafer.

Leksjon 4 av 413 trinn

Network Delay Time og rekonstruksjon av stier er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Problemet Network Delay Time

Network Delay Time (LeetCode 743): Gitt et nettverk med n noder og rettede, vektede kanter som representerer signalets overføringstider, skal De finne den minste tiden det tar for et signal sendt fra node k å nå alle noder. Hvis en node ikke kan nås, returneres -1. Dette er en direkte anvendelse av Dijkstra: svaret er den største korteste-stiavstanden fra k til alle noder.

Løsning: Dijkstra + maksimum av avstandene

Kjør Dijkstra fra kilden k for å finne dist[v] for alle noder v. Svaret er max(dist.values()). Hvis en dist[v] fortsatt er inf, kan den noden ikke nås – returner -1. Signalet følger alle stier samtidig, så flaskehalsen er noden det tar lengst tid å nå.

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

Gjenoppbygging av sti med prev-array

For å gjenoppbygge den faktiske korteste stien samtidig som avstandene beregnes, vedlikeholder De en prev-ordbok som registrerer den beste forgjengeren for hver node. Hver gang dist[v] oppdateres, setter De prev[v] = u. Når Dijkstra er ferdig, følger De pekerne bakover fra målet gjennom prev til kilden er nådd, og snur deretter rekkefølgen for å få stien i riktig retning.

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]

Toveis BFS for store uvektede grafer

For store uvektede grafer der det bare trengs én kilde–mål-parrelasjon, kan toveis BFS være betydelig raskere enn standard BFS. Algoritmen kjører BFS samtidig fra kilden og målet og stopper når de to frontene møtes. I praksis blir hastighetsøkningen betydelig fordi hver front bare trenger å utforske halvparten av grafdybden – antallet utforskede noder reduseres fra O(b^d) til O(2 × b^(d/2)), der b er forgreningsfaktoren.

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

Når De bør velge hvilken algoritme

Veiledning for valg: Uvektet graf, ett par → BFS eller toveis BFS. Vektet, ikke-negative vekter, én kilde → Dijkstra. Vektet, muligens negative vekter, én kilde → Bellman-Ford. Alle par → Floyd-Warshall (liten V) eller V × Dijkstra (glissen graf). Begrenset antall hopp → Modifisert Bellman-Ford med et begrenset antall gjennomløp. Å forklare denne begrunnelsen høyt i intervjuer viser algoritmisk modenhet.

Finn byen med færrest nåbare nabobyer (LeetCode 1334)

Gitt byer med vektede veier og en distanceThreshold skal De finne byen som kan nås fra færrest andre byer innenfor terskelen (ved likhet velges den største byindeksen). Løsning: beregn de korteste stiene mellom alle par med Floyd-Warshall, og tell deretter for hver by hvor mange andre byer som kan nås innenfor terskelen. Returner byen med det laveste antallet (ved likhet: høyeste indeks).

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

Sti i en vektet DAG

For en rettet asyklisk graf (DAG) kan korteste (eller lengste) stier finnes ved hjelp av topologisk sortering + relaksering i O(V+E) – raskere enn Dijkstra. Behandle nodene i topologisk rekkefølge. Når node u behandles, relakserer De alle utgående kanter. For lengste stier (nyttig ved prosjektplanlegging eller kritisk sti) kan vektene negeres, eller min kan endres til 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

Korteste sti i en matrise med hindringer

En vanlig variant i intervjuer er å finne den korteste stien i et 2D-rutenett fra øvre venstre til nedre høyre hjørne, der celler kan være blokkerte. Dette er et ubevektet BFS-problem (hvert steg koster 1). Bruk BFS med bevegelse i fire retninger, og marker celler som besøkt når de legges i køen (ikke når de tas ut av køen) for å unngå gjentatte besøk. Hvis det er mulig å bevege seg gjennom hindringer mot en kostnad, bruk Dijkstra på 2D-rutenettet og betrakt det som en vektet graf.

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 med flere kilder

Når det finnes flere startpunkter (for eksempel flere «porter» i et rutenett eller flere opphav i et kart), kjører De BFS med flere kilder: legg alle kildene i køen med avstand 0 samtidig. Dette beregner den korteste avstanden fra den nærmeste kilden til hver celle i ett BFS-gjennomløp. Teknikken unngår å kjøre BFS separat fra hver kilde og har total tidskompleksitet O(V+E).

Oppsummering av algoritmevalg

Et kort beslutningstre: én kilde, ikke-negative vekter → Dijkstra O((V+E) log V). Én kilde, negative vekter → Bellman-Ford O(VE). Alle par, liten V → Floyd-Warshall O(V³). DAG, vilkårlige vekter → Topologisk sortering + relaksering O(V+E). Uvektet → BFS O(V+E). Stier i rutenett → BFS (uvektet) eller Dijkstra med heap (vektet). Husk denne tabellen – den besvarer oppfølgingsspørsmål i alle intervjuer om korteste stier.

Stifinning i intervjuspørsmål

Mange intervjuspørsmål ber om den faktiske stien, ikke bare kostnaden. Avklar alltid: er det nødvendig å finne stien, eller er avstanden tilstrekkelig? Hvis stien trengs, opprett en prev-ordbok fra starten. Vanlige feil er å glemme å initialisere prev[source] = None som avslutningsbetingelse og å forveksle rekkefølgen ved gjenoppbyggingen (spor bakover fra målet til kilden, og snu deretter rekkefølgen). Øv på å gjenoppbygge stier i eksempler med 3–4 noder før De bruker metoden på større problemer.

Hurtigsjekk

Test Deres forståelse av begrepene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De: Network Delay Time løses med max(dist.values()) etter Dijkstra, gjenoppbygging av stier bruker en prev-tabell som oppdateres hver gang dist[v] forbedres, og toveis BFS kan halvere søkeområdet for uvektede korteste stier mellom ett kilde–mål-par. Neste tema er grafordning med Kahns algoritme for topologisk sortering.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Network Delay Time og rekonstruksjon av stier» gratis?

Ja – hele teksten i «Network Delay Time og rekonstruksjon av stier» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Network Delay Time og rekonstruksjon av stier»?

Løs «network-delay-time» med Dijkstra, rekonstruer den faktiske korteste stien ved hjelp av et forgjengerkart, og se på toveis BFS for store grafer. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Network Delay Time og rekonstruksjon av stier»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

Dijkstras algoritme med prioritetskø
Bellman-Ford og negative sykler
Floyd-Warshall: Korteste stier mellom alle par
Network Delay Time og rekonstruksjon av stier

← Tilbake til Forberedelse til kodeintervjuer