Network Delay Time och återskapande av vägar
Lös network-delay-time med Dijkstra, återskapa den faktiska kortaste vägen med en föregångarkarta och diskutera bidirectional BFS för stora grafer.
Network Delay Time och återskapande av vägar är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Problemet Network Delay Time
Network Delay Time (LeetCode 743): givet ett nätverk med n noder och riktade, viktade kanter som representerar signalens överföringstider, hitta den minsta tid det tar för en signal som skickas från nod k att nå alla noder. Om någon nod inte kan nås ska ni returnera -1. Detta är en direkt tillämpning av Dijkstra: svaret är det största kortaste vägsavståndet från k till någon nod.
Lösning: Dijkstra + största avståndet
Kör Dijkstra från källan k för att hitta dist[v] för alla noder v. Svaret är max(dist.values()). Om något dist[v] fortfarande är inf kan noden inte nås – returnera -1. Signalen färdas längs alla vägar samtidigt, så flaskhalsen är den nod som tar längst tid att 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Återskapa vägen med en prev-array
Om ni vill återskapa den faktiska kortaste vägen samtidigt som ni beräknar avstånden ska ni underhålla en ordbok med namnet prev som registrerar den bästa föregångaren för varje nod. Varje gång ni uppdaterar dist[v] ska ni ange prev[v] = u. När Dijkstra har slutförts följer ni pekarna i prev bakåt från målet tills ni når källan och vänder sedan på resultatet för att få vägen i rätt riktning.
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]Dubbelriktad BFS för stora oviktade grafer
För stora oviktade grafer där ni bara behöver hitta en enda källa–mål-förbindelse kan dubbelriktad BFS vara betydligt snabbare än vanlig BFS. Algoritmen kör samtidigt BFS från källan och målet och stannar när de två fronterna möts. I praktiken blir hastighetsökningen betydande eftersom varje front bara behöver utforska halva grafdjupet – antalet utforskade noder minskar från O(b^d) till O(2 × b^(d/2)), där b är förgreningsfaktorn.
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 -1När ni ska välja algoritm
Beslutsguide: Oviktad graf, ett enda nodpar → BFS eller dubbelriktad BFS. Viktad graf, icke-negativa vikter, en enda källa → Dijkstra. Viktad graf, eventuellt negativa vikter, en enda källa → Bellman-Ford. Alla nodpar → Floyd-Warshall (litet V) eller V × Dijkstra (gles graf). Begränsat antal steg → Modifierad Bellman-Ford med begränsat antal genomgångar. Om ni förklarar denna beslutslogik högt under intervjuer visar ni prov på algoritmisk mognad.
Hitta staden med minst antal nåbara grannar (LeetCode 1334)
Givet städer med viktade vägar och en distanceThreshold ska ni hitta den stad som kan nås från minst antal andra städer inom tröskelvärdet (välj staden med högre stadsindex vid lika resultat). Lösning: beräkna kortaste vägar mellan alla nodpar med Floyd-Warshall och räkna sedan för varje stad hur många andra städer som kan nås inom tröskelvärdet. Returnera staden med det minsta antalet (vid lika resultat: högsta 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)) # 3Väg i en viktad DAG
För en riktad acyklisk graf (DAG) kan ni hitta kortaste (eller längsta) vägar genom topologisk sortering och relaxering i O(V+E) – snabbare än Dijkstra. Bearbeta noderna i topologisk ordning; när ni bearbetar nod u relaxerar ni alla utgående kanter. För längsta vägar (användbart vid projektplanering och för att hitta den kritiska linjen) kan ni byta tecken på vikterna eller ändra min till 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 distKortaste vägen i en matris med hinder
En vanlig intervjuvariant är att hitta den kortaste vägen i ett tvådimensionellt rutnät från det övre vänstra hörnet till det nedre högra, där vissa celler kan vara blockerade. Detta är ett oviktat BFS-problem (varje steg kostar 1). Använd BFS med rörelse i fyra riktningar och markera celler som besökta när de läggs i kön (inte när de tas ur kön) för att undvika återbesök. Om det går att ta sig genom hinder mot en kostnad ska ni använda Dijkstra på det tvådimensionella rutnätet och behandla det som en viktad 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]])) # 4BFS från flera källor
När det finns flera startpunkter (till exempel flera ”grindar” i ett rutnät eller flera ursprung på en karta) kör ni BFS från flera källor: lägg samtidigt alla källor i kön med avståndet 0. Då beräknas det kortaste avståndet från den närmaste källan till varje cell i en enda BFS-genomgång. Tekniken undviker att BFS körs separat från varje källa och har den totala tidskomplexiteten O(V+E).
Sammanfattning av algoritmval
En kort beslutsöversikt: en källa, icke-negativa vikter → Dijkstra O((V+E) log V). En källa, negativa vikter → Bellman-Ford O(VE). Alla nodpar, litet V → Floyd-Warshall O(V³). DAG, godtyckliga vikter → Topologisk sortering + relaxering O(V+E). Oviktad graf → BFS O(V+E). Vägar i rutnät → BFS (oviktad) eller Dijkstra med heap (viktad). Lär er denna tabell utantill – den besvarar följdfrågor i alla intervjuer om kortaste vägar.
Att hitta vägar i intervjufrågor
Många intervjuproblem kräver den faktiska vägen, inte bara kostnaden. Klargör alltid: behöver ni vägen eller bara avståndet? Om vägen behövs ska ni skapa en prev-ordbok från början. Vanliga misstag är att glömma att initiera prev[source] = None som slutvillkor och att blanda ihop ordningen vid återskapandet (följ vägen bakåt från målet till källan och vänd sedan på den). Öva på att återskapa vägar i exempel med 3–4 noder innan ni går vidare till större problem.
Snabb kontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen har ni lärt er att Network Delay Time besvaras med max(dist.values()) efter Dijkstra, att återskapande av vägar använder en prev-array som uppdateras varje gång dist[v] förbättras och att dubbelriktad BFS kan halvera sökutrymmet för oviktade kortaste vägar mellan ett enda nodpar. Därefter går vi vidare till grafordning med Kahns algoritm för topologisk sortering.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Network Delay Time och återskapande av vägar” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Network Delay Time och återskapande av vägar”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Network Delay Time och återskapande av vägar”?
Lös network-delay-time med Dijkstra, återskapa den faktiska kortaste vägen med en föregångarkarta och diskutera bidirectional BFS för stora grafer. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Network Delay Time och återskapande av vägar”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Dijkstras algoritm med en prioritetskö
- Bellman-Ford och negativa cykler
- Floyd-Warshall: kortaste vägar mellan alla par
- Network Delay Time och återskapande av vägar