Network Delay Time

Q: Qual è la complessità temporale di Network Delay Time?

Con l'algoritmo di Dijkstra e un heap binario, la complessità è O(E log E), dove E è il numero di collegamenti. È lo stesso di O(E log n), poiché E è al massimo n². La lista di adiacenza, i tempi e l'heap occupano O(n + E) spazio. Bellman-Ford richiede O(n · E) tempo e O(n) spazio.

Q: Perché l'algoritmo di Dijkstra ha bisogno di pesi non negativi?

Dijkstra fissa il nodo con il tempo provvisorio più piccolo e non lo esamina più. Questo è sicuro solo se nessun percorso successivo può essere più breve e, con pesi non negativi, ogni percorso che passa per un nodo non ancora fissato costa almeno quanto il tempo di quel nodo. Un collegamento negativo invalida questo ragionamento: un percorso che passa per un nodo che sembrava più costoso può comunque risultare più economico. Per i pesi negativi, usa Bellman-Ford.

Q: Perché non usare BFS per il tempo di propagazione nella rete?

BFS visita i nodi in base al numero di collegamenti che li separano dall'inizio; questo corrisponde all'ordine di arrivo solo quando tutti i collegamenti richiedono lo stesso tempo. Qui i tempi dei collegamenti sono diversi, quindi un percorso con più collegamenti può arrivare prima. Se tutti i tempi fossero uguali, BFS sarebbe sufficiente; con tempi pari solo a 0 e 1, funziona una BFS 0-1 basata su deque.

Q: Riesci a risolvere Network Delay Time senza un heap?

Sì. Dijkstra con un array semplice esamina ogni nodo non ancora stabilizzato per trovare il tempo minimo, con un costo totale di O(n²) e senza bisogno di un heap. È la scelta migliore nei grafi densi, dove E è vicino a n². Nei grafi sparsi, come i grandi test qui con 3,000 nodi e 4,000 collegamenti, la versione con heap richiede molto meno lavoro.

MedioCammini minimi Grafi Heap

+10

Una rete ha n nodi, numerati da 1 a n. I suoi collegamenti sono forniti come un elenco times, dove times[i] = [u, v, w] significa che un segnale inviato dal nodo u raggiunge il nodo v dopo w unità di tempo. I collegamenti funzionano in una sola direzione.

Un segnale parte dal nodo k al tempo 0 e viaggia lungo tutti i collegamenti che può raggiungere. Restituisci il tempo in cui lo riceve l'ultimo nodo, oppure -1 se un nodo non lo riceve mai.

Funzione

networkDelayTime(times: integer-2d-array, n: integer, k: integer) → integer

timesinteger-2d-array: i collegamenti diretti, 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 ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n e u ≠ v
0 ≤ w ≤ 100
Nessuna coppia di collegamenti condivide gli stessi u e v.
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 nodo 3 riceve il segnale al tempo 1. Il nodo 2 potrebbe riceverlo al tempo 4 tramite il collegamento diretto, ma il percorso attraverso il nodo 3 arriva a 1 + 2 = 3, e il nodo 4 lo riceve a 3 + 1 = 4. Il nodo 4 è l’ultimo, al tempo 4.

+16 test nascosti all’invio

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ù.

0 di 3 aperti

Soluzione

Ogni nodo riceve il segnale dopo un tempo pari alla lunghezza del percorso più veloce da k, quindi il compito consiste nel trovare i cammini minimi a sorgente singola in un grafo orientato, seguiti da un massimo. La risposta è il tempo minimo più lungo oppure -1 se non esiste un percorso per qualche nodo. I tempi dei collegamenti non sono mai negativi, il che permette all’algoritmo di Dijkstra di fissare ogni nodo una sola volta, in ordine di arrivo, usando un min-heap. Qui sotto, E è il numero di collegamenti, times.length.

Ricerca in profondità che rivisita ogni volta che trova un percorso più veloce

Corretto, ma non termina sui test più grandi

Intuizione

Avvia una ricerca dal nodo k con tempo 0 e segui ogni collegamento, tenendo traccia del tempo trascorso. Registra, per ogni nodo, il tempo di arrivo più breve trovato. Quando la ricerca raggiunge un nodo in un tempo pari o superiore a quello registrato, fermati lì: tutto ciò che quel percorso potrebbe offrire più avanti è già stato offerto dal percorso più veloce. Quando invece raggiunge il nodo in un tempo minore, il record migliora e anche tutto ciò che si trova oltre il nodo potrebbe migliorare, quindi la ricerca riparte da lì.

Questo è sempre corretto. La ricerca si ferma solo quando nessun percorso migliora alcun record e il percorso più veloce per ogni nodo migliora il record di quel nodo a un certo punto, quindi ogni record termina per indicare il tempo più veloce effettivo.

Il problema è quante volte può migliorare un nodo. Una ricerca in profondità segue il primo collegamento che incontra fino in fondo, quindi può raggiungere un nodo con un percorso lento, poi con uno leggermente più veloce e poi ancora con uno più veloce, ripercorrendo ogni volta tutto ciò che si trova oltre il nodo. Immagina 18 cancelli in fila. Tra ogni coppia di cancelli puoi prendere un collegamento gratuito oppure una deviazione: una catena di collegamenti i cui tempi sommano a 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, ciascuno più breve del precedente, e percorre ogni volta i 1,700 nodi che si trovano oltre: circa 220 milioni di passaggi. Due dei test più grandi sono costruiti in questo modo, uno con ogni deviazione elencata prima del collegamento gratuito e uno con la deviazione elencata dopo, così la ricerca inciampa in uno dei due qualunque sia l’ordine in cui prova i collegamenti.

Algoritmo

Crea una lista di adiacenza: per ogni nodo, i collegamenti che ne partono con i relativi tempi.
Imposta il tempo migliore di ogni nodo a infinito e inserisci (k, 0) in uno stack.
Estrai (node, t). Se t non è inferiore a best[node], saltalo; altrimenti imposta best[node] = t.
Inserisci (next, t + w) per ogni collegamento da node il cui arrivo è migliore di best[next].
Quando lo stack è vuoto, restituisci -1 se un qualsiasi tempo migliore è ancora 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 worst

Bellman-Ford: rilassa ogni collegamento fino a n-1 volte

Intuizione

Mantieni un tempo provvisorio dist per ogni nodo: 0 per k, infinito per gli altri. Rilassare un collegamento u → v con tempo w significa: se dist[u] + w è minore di dist[v], il collegamento offre un percorso più rapido per raggiungere v, quindi riduci dist[v] a quel valore. Bellman-Ford esegue passate sull’intero elenco e rilassa ogni collegamento a ogni passata.

Perché così si ottengono i tempi corretti? Prendi il percorso più rapido per raggiungere un nodo, per esempio k → a → b → v. La prima passata rilassa k → a mentre dist[k] è già 0, quindi al termine dist[a] è definitivo. La seconda passata rende definitivo dist[b], la terza dist[v]. Un percorso più rapido non deve mai visitare due volte lo stesso nodo, perché un ciclo non richiede mai un tempo negativo: quindi ha al massimo n-1 collegamenti e n-1 passate determinano il valore di ogni nodo. Una passata che non modifica nulla dimostra che nessuna passata successiva potrà farlo, quindi ti fermi lì.

Ogni passata ha un costo O(E), quindi nel caso peggiore il costo è O(n · E). L’ordine dell’elenco determina quanto può peggiorare: se i collegamenti di un lungo percorso sono elencati partendo dall’estremità più lontana e procedendo verso l’inizio, ogni passata determina il valore di un nodo in più. Un test di grandi dimensioni è proprio questo: una catena di 3,000 nodi elencata al contrario, che richiede 2,999 passate su 4,000 collegamenti: circa 12 milioni di rilassamenti. Per queste dimensioni l’esecuzione è comunque abbastanza rapida, ma il lavoro cresce in proporzione a n per E. Il punto di forza di Bellman-Ford è un altro: resta corretto quando i tempi di alcuni collegamenti sono negativi, mentre Dijkstra fallisce.

Algoritmo

Imposta dist[k] = 0 e tutti gli altri dist a infinito.
Ripeti fino a n-1 volte: per ogni collegamento [u, v, w], se dist[u] + w < dist[v], imposta dist[v] = dist[u] + w.
Interrompi in anticipo dopo un passaggio che non apporta modifiche.
Restituisci -1 se 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 worst

Algoritmo di Dijkstra con un heap minimo

Intuizione

Bellman-Ford spreca passaggi perché rilassa i collegamenti in uscita dai nodi i cui tempi non sono ancora definitivi, e deve tornarci in seguito. L'algoritmo di Dijkstra rilassa i collegamenti di ciascun nodo esattamente una volta, nel momento in cui il suo tempo diventa definitivo. La domanda è come sapere quando succede.

La risposta è una regola greedy: tra i nodi non ancora definitivi, quello con il tempo provvisorio minore è già definitivo. Qualsiasi altro percorso verso di esso deve uscire dai nodi definitivi a un certo punto, passando per un nodo non definitivo il cui tempo è almeno altrettanto grande, e i collegamenti successivi possono solo aggiungere tempo, perché nessuno è negativo. Quindi rendi definitivo quel nodo, rilassi i suoi collegamenti e ripeti. Nel primo esempio, il nodo 1 diventa definitivo a 0 e offre al nodo 2 il tempo 4 e al nodo 3 il tempo 1. Il nodo 3 è quello con il tempo minore, diventa definitivo a 1 e abbassa il tempo del nodo 2 a 3. Il nodo 2 diventa definitivo a 3 e offre al nodo 4 il tempo 4, che diventa definitivo per ultimo. La risposta è 4.

Un min-heap trova rapidamente il tempo provvisorio minore. Inserisci (time, node) ogni volta che il tempo di un nodo migliora e lascia la voce precedente nell'heap invece di cercarla. Quando la voce precedente esce più tardi, il suo tempo è superiore al tempo attuale del nodo, quindi la salti. Ogni collegamento inserisce al massimo una voce, quindi l'heap non contiene mai più di E + 1 voci, e ogni inserimento o estrazione costa O(log E). Il costo totale è quindi O(E log E), con spazio O(n + E) per la lista di adiacenza, i tempi e l'heap.

Sono i tempi non negativi a rendere sicura la regola greedy. Considera i collegamenti A → B con tempo 2, A → C con tempo 3 e C → B con tempo -2. Dijkstra rende definitivo B a 2, eppure il percorso attraverso C lo raggiunge a 1. Un segnale non può mai arrivare prima di essere inviato, quindi qui ogni tempo è almeno 0 e la regola è valida.

Algoritmo

Crea una lista di adiacenza di coppie (next, w) per ogni nodo.
Imposta dist[k] = 0, ogni altro dist a infinito e inserisci (0, k) in un min-heap.
Estrai il più piccolo (t, node). Se t > dist[node], la voce è obsoleta: saltala.
Altrimenti t è definitivo. Per ogni collegamento da node a next con tempo w, se t + w < dist[next], imposta dist[next] = t + w e inserisci (t + w, next).
Quando l'heap è vuoto, restituisci -1 se uno qualsiasi dei valori dist è infinito; altrimenti, restituisci il 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

La maggior parte dei bug ignora la direzione dei collegamenti, si fida del primo tempo assegnato a un nodo o perde di vista i nodi che il segnale non raggiunge mai.

Considerare i collegamenti bidirezionali. [3, 1, 2] trasmette il segnale solo da 3 a 1, motivo per cui il nodo 3 non lo riceve mai nel secondo esempio.
Usare la ricerca in ampiezza semplice. Trova il percorso con il minor numero di collegamenti, non quello più veloce: nel primo esempio assegna al nodo 2 il tempo 4 passando per il collegamento diretto, invece di 3 passando per il nodo 3.
Considerare definitivo un nodo quando viene inserito, invece che quando viene estratto. Il primo tempo assegnato a un nodo non è sempre il migliore; solo la voce minima estratta dall'heap è definitiva.
Dimenticare il -1. Calcolare il massimo senza controllare restituisce l'infinito oppure indica il tempo finito più grande, nascondendo il nodo che non ha mai ricevuto il segnale.
Numerare i nodi a partire da 0. I nodi sono etichettati da 1 a n, quindi dimensiona gli array n+1 ed escludi dallo spazio massimo la posizione 0, che non viene usata.
Overflow causato dall'infinito. Se l'infinito è il valore int più grande, dist[u] + w diventa un numero negativo per un u non raggiunto. Salta i nodi non raggiunti oppure usa un valore come 10^9 che lasci un margine.

Domande frequenti4

Qual è la complessità temporale di Network Delay Time?

Con l'algoritmo di Dijkstra e un heap binario, la complessità è O(E log E), dove E è il numero di collegamenti. È lo stesso di O(E log n), poiché E è al massimo n². La lista di adiacenza, i tempi e l'heap occupano O(n + E) spazio. Bellman-Ford richiede O(n · E) tempo e O(n) spazio.

Perché l'algoritmo di Dijkstra ha bisogno di pesi non negativi?

Dijkstra fissa il nodo con il tempo provvisorio più piccolo e non lo esamina più. Questo è sicuro solo se nessun percorso successivo può essere più breve e, con pesi non negativi, ogni percorso che passa per un nodo non ancora fissato costa almeno quanto il tempo di quel nodo. Un collegamento negativo invalida questo ragionamento: un percorso che passa per un nodo che sembrava più costoso può comunque risultare più economico. Per i pesi negativi, usa Bellman-Ford.

Perché non usare BFS per il tempo di propagazione nella rete?

BFS visita i nodi in base al numero di collegamenti che li separano dall'inizio; questo corrisponde all'ordine di arrivo solo quando tutti i collegamenti richiedono lo stesso tempo. Qui i tempi dei collegamenti sono diversi, quindi un percorso con più collegamenti può arrivare prima. Se tutti i tempi fossero uguali, BFS sarebbe sufficiente; con tempi pari solo a 0 e 1, funziona una BFS 0-1 basata su deque.

Riesci a risolvere Network Delay Time senza un heap?

Sì. Dijkstra con un array semplice esamina ogni nodo non ancora stabilizzato per trovare il tempo minimo, con un costo totale di O(n²) e senza bisogno di un heap. È la scelta migliore nei grafi densi, dove E è vicino a n². Nei grafi sparsi, come i grandi test qui con 3,000 nodi e 4,000 collegamenti, la versione con heap richiede molto meno lavoro.

Python

def networkDelayTime(times, n, k):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]
n = 4
k = 1

Atteso

Network Delay Time

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Ricerca in profondità che rivisita ogni volta che trova un percorso più veloce

Bellman-Ford: rilassa ogni collegamento fino a n-1 volte

Algoritmo di Dijkstra con un heap minimo

Trappole e casi limite

Domande frequenti4

Problemi simili