Network Delay Time e ricostruzione del percorso
Risolva network-delay-time con Dijkstra, ricostruisca l'effettivo cammino minimo usando una mappa dei predecessori e analizzi la BFS bidirezionale per i grafi di grandi dimensioni.
Network Delay Time e ricostruzione del percorso è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Problema Network Delay Time
Network Delay Time (LeetCode 743): data una rete con n nodi e archi orientati pesati che rappresentano i tempi di trasmissione del segnale, trovi il tempo minimo necessario affinché un segnale inviato dal nodo k raggiunga tutti i nodi. Se un nodo è irraggiungibile, restituisca -1. Si tratta di un'applicazione diretta di Dijkstra: la risposta è la massima distanza di un percorso minimo da k tra tutti i nodi.
Soluzione: Dijkstra + massimo delle distanze
Esegua Dijkstra dalla sorgente k per trovare dist[v] per tutti i nodi v. La risposta è max(dist.values()). Se un qualsiasi dist[v] è ancora inf, quel nodo è irraggiungibile: restituisca -1. Il segnale percorre tutti i cammini simultaneamente, quindi il collo di bottiglia è il nodo che richiede più tempo per essere raggiunto.
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)) # 2Ricostruzione del percorso con l'array prev
Per ricostruire il percorso minimo effettivo insieme al calcolo delle distanze, mantenga un dizionario prev che memorizzi il predecessore migliore per ogni nodo. Ogni volta che aggiorna dist[v], imposti prev[v] = u. Al termine di Dijkstra, segua a ritroso i puntatori di prev dalla destinazione finché non raggiunge la sorgente, quindi inverta il risultato per ottenere il percorso in avanti.
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]BFS bidirezionale per grafi non pesati di grandi dimensioni
Per i grafi non pesati di grandi dimensioni in cui serve trovare un solo percorso tra una sorgente e una destinazione, la BFS bidirezionale può essere significativamente più veloce della BFS standard. Esegue contemporaneamente una BFS dalla sorgente e una dalla destinazione, fermandosi quando le due frontiere si incontrano. Il miglioramento pratico è significativo perché ciascuna frontiera deve esplorare solo metà della profondità del grafo, riducendo i nodi visitati da O(b^d) a O(2 × b^(d/2)), dove b è il fattore di ramificazione.
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 -1Quando scegliere ciascun algoritmo
Guida alla scelta: grafo non pesato, singola coppia → BFS o BFS bidirezionale. Grafo pesato, pesi non negativi, singola sorgente → Dijkstra. Grafo pesato, pesi potenzialmente negativi, singola sorgente → Bellman-Ford. Tutte le coppie → Floyd-Warshall (V piccolo) oppure V × Dijkstra (grafo sparso). Numero di passaggi vincolato → Bellman-Ford modificato con un numero limitato di passaggi. Esporre ad alta voce questa motivazione durante i colloqui dimostra una solida maturità algoritmica.
Trova la città con il minor numero di vicini raggiungibili (LeetCode 1334)
Date alcune città collegate da percorsi pesati e una distanceThreshold, trovi la città raggiungibile dal minor numero di altre città entro tale soglia (in caso di parità, preferisca l'indice di città maggiore). Soluzione: calcoli i percorsi minimi tra tutte le coppie con Floyd-Warshall, quindi conti per ogni città quante altre città sono raggiungibili entro la soglia. Restituisca la città con il conteggio minimo (in caso di parità: indice massimo).
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)) # 3Percorso in un DAG pesato
Per un grafo aciclico diretto (DAG), i percorsi minimi (o massimi) possono essere trovati con l'ordinamento topologico e il rilassamento in O(V+E), più velocemente che con Dijkstra. Elabori i nodi nell'ordine topologico; quando elabora il nodo u, rilassi tutti gli archi uscenti. Per i percorsi massimi (utili nella pianificazione dei progetti e nel percorso critico), neghi i pesi oppure sostituisca min con 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 distPercorso minimo in una matrice con ostacoli
Una variante comune nei colloqui consiste nel trovare il percorso minimo in una griglia 2D dall'angolo superiore sinistro a quello inferiore destro, dove alcune celle possono essere bloccate. Si tratta di un problema di BFS non pesata (ogni passo ha costo 1). Utilizzi una BFS con movimento nelle 4 direzioni, contrassegnando le celle come visitate quando vengono accodate (non quando vengono estratte dalla coda) per evitare di visitarle nuovamente. Se è possibile attraversare gli ostacoli pagando un costo, utilizzi Dijkstra sulla griglia 2D, trattandola come un grafo pesato.
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 multi-sorgente
Quando esistono più punti di partenza (ad esempio, più «porte» in una griglia o più origini in una mappa), esegua una BFS multi-sorgente: accodi simultaneamente tutte le sorgenti con distanza 0. In questo modo calcola, con un'unica BFS, la distanza minima dalla sorgente più vicina a ogni cella. Questa tecnica evita di eseguire una BFS separata per ogni sorgente e ha complessità totale O(V+E).
Riepilogo della scelta dell'algoritmo
Un albero decisionale conciso: sorgente singola, pesi non negativi → Dijkstra O((V+E) log V). Sorgente singola, pesi negativi → Bellman-Ford O(VE). Tutte le coppie, V piccolo → Floyd-Warshall O(V³). DAG, pesi qualsiasi → ordinamento topologico + rilassamento O(V+E). Grafo non pesato → BFS O(V+E). Percorsi su griglia → BFS (non pesata) o Dijkstra con heap (pesata). Memorizzi questa tabella: risponde alle domande di approfondimento in qualsiasi colloquio sui percorsi minimi.
Ricerca di percorsi nelle domande dei colloqui
Molti problemi dei colloqui chiedono il percorso effettivo, non solo il costo. Chiarisca sempre: serve il percorso o è sufficiente la distanza? Se serve il percorso, allochi un dizionario prev fin dall'inizio. Errori comuni: dimenticare di inizializzare prev[source] = None come condizione terminale e confondere l'ordine di ricostruzione (tracciare a ritroso dalla destinazione alla sorgente, quindi invertire). Si eserciti a ricostruire percorsi su esempi con 3-4 nodi prima di applicare la tecnica a problemi più grandi.
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: Network Delay Time si risolve con max(dist.values()) dopo Dijkstra, la ricostruzione del percorso utilizza un array prev aggiornato ogni volta che dist[v] migliora e la BFS bidirezionale può dimezzare lo spazio di ricerca per i percorsi minimi non pesati tra una singola coppia. Ora passeremo all'ordinamento dei grafi con l'algoritmo di Kahn per l'ordinamento topologico.
Domande Frequenti
La lezione «Network Delay Time e ricostruzione del percorso» è gratuita?
Sì — il testo completo di «Network Delay Time e ricostruzione del percorso» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Network Delay Time e ricostruzione del percorso»?
Risolva network-delay-time con Dijkstra, ricostruisca l'effettivo cammino minimo usando una mappa dei predecessori e analizzi la BFS bidirezionale per i grafi di grandi dimensioni. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Network Delay Time e ricostruzione del percorso»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Algoritmo di Dijkstra con coda di priorità
- Bellman-Ford e cicli negativi
- Floyd-Warshall: cammini minimi tra tutte le coppie
- Network Delay Time e ricostruzione del percorso