Network Delay Time
Una rete ha n nodi etichettati da 1 a n. Il collegamento times[i] = [u, v, w] trasmette un segnale dal nodo u al nodo v in w unità di tempo, solo in quella direzione.
Un segnale parte dal nodo k al tempo 0 e viaggia lungo ogni collegamento possibile. Restituisci il tempo in cui lo riceve l'ultimo nodo oppure -1 se un nodo non lo riceve mai.
Funzione
- timesinteger-2d-array
- i collegamenti orientati, ciascuno come [u, v, w]
- ninteger
- il numero di nodi
- kinteger
- il nodo che invia il segnale
- Restituisceinteger
- il momento in cui l’ultimo nodo riceve il segnale, oppure -1
Vincoli
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ neu ≠ v0 ≤ w ≤ 100- Nessuna coppia di collegamenti condivide sia lo stesso
usia lo stessov. 1 ≤ k ≤ n
Esempi
- Input
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Output
- 4
- Spiegazione
- Il collegamento diretto raggiunge il nodo 2 al tempo 4, ma il percorso attraverso il nodo 3 arriva a 1 + 2 = 3. Il nodo 4 riceve il segnale per ultimo, a 3 + 1 = 4.
- Input
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Output
- -1
- Spiegazione
- Il nodo 2 riceve il segnale al tempo 3, ma l’unico collegamento che tocca il nodo 3 va da 3 a 1. Il nodo 3 non lo riceve mai, quindi la risposta è -1.
- Input
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Output
- 2
- Spiegazione
- Il collegamento al nodo 3 impiega 0, quindi il nodo 3 riceve il segnale al tempo 0. Il nodo 1 lo riceve poi al tempo 0 + 2 = 2, prima che dopo i 5 del collegamento diretto.
Per approfondire
Supponiamo che il segnale si attenui dopo aver attraversato m collegamenti. Come trovi il tempo in cui l'ultimo nodo lo sente entro quel limite?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Un nodo riceve il segnale dopo il tempo necessario a percorrere il percorso più veloce per raggiungerlo da
k. Quindi, la risposta è il più grande di questi tempi minimi, oppure -1 se non esiste alcun percorso per qualche nodo.Nessun collegamento richiede un tempo negativo. Quindi, tra i nodi il cui tempo non è ancora definitivo, quello con il tempo provvisorio più piccolo non può essere raggiunto più rapidamente: ogni altro percorso per raggiungerlo passa per un altro di quei nodi, che viene raggiunto non prima. Fissa i nodi nell’ordine di arrivo.
Mantieni un min-heap di coppie
(time, node). Estrai l'elemento più piccolo, ignoralo se il nodo ha già un tempo inferiore e inserisci ogni vicino per cui il tempo migliora. Quando l'heap è vuoto, prendi il tempo più grande.
Soluzione
Ogni nodo riceve il segnale dopo un tempo pari alla lunghezza del percorso più veloce da k, quindi si tratta di trovare i percorsi minimi da una singola sorgente e poi il massimo, oppure -1 quando un nodo non è raggiungibile. I tempi dei collegamenti non sono mai negativi, quindi l'algoritmo di Dijkstra esamina ogni nodo una sola volta. Qui sotto, E è times.length.
Ricerca in profondità che rivisita ogni percorso più veloce
Corretto, ma non termina sui test più grandi
Intuizione
Esplora a partire da k in profondità, tenendo traccia del tempo trascorso e registrando il tempo di arrivo più rapido per ogni nodo. Un percorso che raggiunge un nodo non prima del tempo registrato si ferma; uno più rapido aggiorna il record e continua la ricerca. Ogni record termina con il tempo minimo effettivo, perché il percorso più rapido lo migliora a un certo punto.
Un nodo può essere migliorato molte volte. Disponi 18 cancelli in fila, collegando ogni coppia con un collegamento gratuito e con una deviazione di 65,536, 32,768 e così via fino a 1. Provando prima le deviazioni, la ricerca raggiunge l'ultimo cancello in 131,072 tempi diversi e ogni volta percorre tutto ciò che si trova oltre: lavoro esponenziale in n.
Algoritmo
- Imposta ogni tempo migliore a infinito e inserisci
(k, 0)in una pila. - Estrai
(node, t). Saltalo a meno chet < best[node]; poi impostabest[node] = t. - Inserisci
(next, t + w)per ogni collegamento danodeil cui arrivo è precedente abest[next]. - Quando la pila è vuota, restituisci -1 se uno qualsiasi dei tempi migliori è infinito; altrimenti, restituisci il più grande.
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 worstBellman-Ford: rilassa ogni collegamento fino a n-1 volte
Intuizione
Mantieni un tempo provvisorio dist per ogni nodo, 0 per k. Rilassare un collegamento u → v riduce dist[v] a dist[u] + w quando il valore è minore. Bellman-Ford rilassa ogni collegamento a ogni passaggio.
Prendi il percorso più veloce verso un nodo, per esempio k → a → b → v. Il primo passaggio rende definitivo dist[a], il secondo dist[b], il terzo dist[v]. Un percorso più veloce non ripete mai un nodo, quindi ha al massimo n-1 collegamenti, e n-1 passaggi determinano il valore di ogni nodo.
Ogni passaggio costa O(E). Una catena di 3.000 nodi elencata dall’estremità più lontana all’indietro richiede 2.999 passaggi su 4.000 collegamenti: circa 12 milioni di rilassamenti.
Algoritmo
- Imposta
dist[k] = 0e ogni altrodista infinito. - Ripeti fino a n-1 volte: per ogni collegamento
[u, v, w], sedist[u] + w < dist[v], impostadist[v] = dist[u] + w. - Interrompi in anticipo dopo un passaggio che non modifica nulla.
- Restituisci -1 se un qualsiasi
distè ancora infinito, altrimenti il valore più grande.
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 worstL'algoritmo di Dijkstra con un heap minimo
Intuizione
Tra i nodi non ancora sistemati, quello con il tempo provvisorio più piccolo è già definitivo. Qualsiasi altro percorso per raggiungerlo deve lasciare i nodi sistemati passando per un nodo non sistemato il cui tempo sia almeno altrettanto grande, e i collegamenti successivi aggiungono solo tempo, perché nessuno ha peso negativo. Quindi sistemi quel nodo, rilassi i suoi collegamenti una volta e ripeti.
Un heap minimo trova il tempo più piccolo. Quando il valore di un nodo migliora, inserisci una nuova voce e lascia quella vecchia al suo posto; una voce estratta il cui tempo è maggiore di dist è obsoleta, quindi la salti. Ogni collegamento inserisce al massimo una voce, quindi l’heap contiene al massimo E + 1 voci e il costo totale è O(E log E).
Algoritmo
- Imposta
dist[k] = 0, ogni altrodista infinito e inserisci(0, k)in un min-heap. - Estrai il più piccolo
(t, node); set > dist[node], ignoralo perché è obsoleto. - Per ogni collegamento
node → nextcon tempow, set + w < dist[next], impostadist[next] = t + we inserisci(t + w, next). - Quando l'heap è vuoto, restituisci -1 se qualche
distè infinito, altrimenti restituisci il valore più grande.
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
Trappole e casi limite
- Considerare i collegamenti bidirezionali.
[3, 1, 2]trasmette il segnale solo da 3 a 1, quindi nel secondo esempio il nodo 3 non lo riceve mai. - Usare una semplice ricerca in ampiezza. Trova il percorso con il minor numero di collegamenti: nel primo esempio assegna al nodo 2 il tempo 4 anziché 3.
- Dimenticare il -1. Calcolare il massimo senza un controllo restituisce infinito oppure nasconde il nodo che non ha mai ricevuto il segnale.
- Usare il valore int più grande come infinito.
dist[u] + wva quindi in overflow e diventa un numero negativo per ununon raggiunto; salta i nodi non raggiunti oppure usa 10^9.
Domande frequenti3
Qual è la complessità temporale di Network Delay Time?
Con l'algoritmo di Dijkstra e un heap binario è O(E log E), dove E è il numero di collegamenti. Questo equivale a O(E log n), poiché E è al massimo n². Lo spazio richiesto è O(n + E). Bellman-Ford richiede O(n · E) di tempo.
Perché l'algoritmo di Dijkstra richiede pesi non negativi?
Dijkstra non visita mai di nuovo un nodo già fissato, il che è sicuro solo se nessun percorso successivo può essere più breve. Con collegamenti A → B di durata 2, A → C di durata 3 e C → B di durata -2, fissa B a 2, ma il percorso che passa per C lo raggiunge a 1. Bellman-Ford gestisce le durate negative.
Riesci a risolvere Network Delay Time senza un heap?
Sì. Dijkstra con un array semplice esamina ogni nodo non ancora visitato per trovare il tempo minimo, con un costo totale di O(n²). È più efficiente nei grafi densi, in cui E è vicino a n². Nei grafi sparsi, come quelli con 3.000 nodi e 4.000 collegamenti, la versione con heap richiede molto meno lavoro.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def networkDelayTime(times, n, k):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Output atteso
4