Network Delay Time
Uma rede tem n nós rotulados de 1 a n. O link times[i] = [u, v, w] transporta um sinal do nó u para o nó v em w unidades de tempo, apenas nessa direção.
Um sinal parte do nó k no instante 0 e percorre todos os links que conseguir. Retorne o instante em que o último nó o recebe ou -1 se algum nó nunca o receber.
Função
- timesinteger-2d-array
- as arestas direcionadas, cada uma como [u, v, w]
- ninteger
- o número de nós
- kinteger
- o nó que envia o sinal
- Retornainteger
- o momento em que o último nó recebe o sinal, ou -1
Restrições
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ neu ≠ v0 ≤ w ≤ 100- Não há dois links que compartilhem o mesmo
ue o mesmov. 1 ≤ k ≤ n
Exemplos
- Entrada
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- Saída
- 4
- Explicação
- O link direto chega ao nó 2 no tempo 4, mas a rota pelo nó 3 chega em 1 + 2 = 3. O nó 4 recebe o sinal por último, em 3 + 1 = 4.
- Entrada
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Saída
- -1
- Explicação
- O nó 2 ouve o sinal no instante 3, mas o único link que toca o nó 3 vai de 3 a 1. O nó 3 nunca o ouve, então a resposta é -1.
- Entrada
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Saída
- 2
- Explicação
- O link para o nó 3 leva 0, então o nó 3 recebe o sinal no instante 0. Em seguida, o nó 1 o recebe em 0 + 2 = 2, antes do instante 5 do seu link direto.
Para ir além
Suponha que o sinal desapareça depois de atravessar m links. Como você encontra o tempo em que o último nó o ouve dentro desse limite?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Um nó recebe o sinal no tempo correspondente ao comprimento da rota mais rápida até ele a partir de
k. Portanto, a resposta é o maior desses tempos mais rápidos, ou -1 quando algum nó não tem nenhuma rota.Nenhum link leva um tempo negativo. Portanto, entre os nós cujo tempo ainda não é definitivo, aquele com o menor tempo provisório não pode chegar mais rápido: qualquer outro caminho até ele passa por outro desses nós, que é alcançado tão cedo quanto ou mais tarde. Defina os nós na ordem de chegada.
Mantenha um min-heap de pares
(time, node). Remova o menor, ignore-o se o nó já tiver um tempo menor e insira cada vizinho cujo tempo melhore. Quando o heap estiver vazio, pegue o maior tempo.
Solução
Cada nó recebe o sinal após o tempo correspondente ao comprimento de sua rota mais rápida a partir de k; portanto, trata-se de caminhos mínimos a partir de uma única origem, seguidos de um máximo, ou -1 quando um nó não tem rota. Os tempos das conexões nunca são negativos, então o algoritmo de Dijkstra finaliza cada nó uma única vez. Abaixo, E é times.length.
Busca em profundidade que revisita a cada rota mais rápida
Correta, mas não termina nos maiores testes
Intuição
Pesquise a partir de k em profundidade, carregando o tempo decorrido e registrando a chegada mais rápida a cada nó. Uma rota que chega a um nó em um tempo igual ou posterior ao registrado é interrompida; uma rota mais rápida atualiza o registro e continua a busca. Cada registro termina com o tempo realmente mais rápido, porque a rota mais rápida o atualiza em algum momento.
Um nó pode ser atualizado muitas vezes. Coloque 18 portões em uma fileira, cada par ligado por uma conexão de custo zero e por um desvio de 65,536, 32,768 e assim por diante, até 1. Tentando primeiro os desvios, a busca chega ao último portão em 131,072 tempos diferentes e percorre tudo o que vem depois dele a cada vez: o trabalho é exponencial em n.
Algoritmo
- Defina todos os melhores tempos como infinito e coloque
(k, 0)em uma pilha. - Retire
(node, t). Ignore-o, a menos quet < best[node]; então definabest[node] = t. - Coloque
(next, t + w)na pilha para cada ligação denodecuja chegada seja anterior abest[next]. - Quando a pilha estiver vazia, retorne -1 se algum melhor tempo for infinito; caso contrário, retorne o maior.
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: relaxe cada aresta até n-1 vezes
Intuição
Mantenha um tempo provisório dist por nó, 0 para k. Relaxar uma ligação u → v reduz dist[v] para dist[u] + w quando esse valor é menor. Bellman-Ford relaxa todas as ligações em cada passagem.
Pegue a rota mais rápida até um nó, digamos k → a → b → v. A primeira passagem torna dist[a] definitivo, a segunda, dist[b], e a terceira, dist[v]. Uma rota mais rápida nunca repete um nó, então tem no máximo n-1 ligações, e n-1 passagens definem todos os nós.
Cada passagem custa O(E). Uma cadeia de 3.000 nós listada da extremidade mais distante para trás exige 2.999 passagens por 4.000 ligações: cerca de 12 milhões de relaxamentos.
Algoritmo
- Defina
dist[k] = 0e todas as outrasdistcomo infinito. - Repita até n-1 vezes: para cada ligação
[u, v, w], sedist[u] + w < dist[v], definadist[v] = dist[u] + w. - Pare mais cedo após uma passagem que não alterar nada.
- Retorne -1 se algum
distainda for infinito; caso contrário, o maior deles.
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 worstAlgoritmo de Dijkstra com um heap mínimo
Intuição
Entre os nós ainda não definidos, aquele com o menor tempo provisório já é definitivo. Qualquer outro caminho até ele precisa sair dos nós já definidos por um nó ainda não definido cujo tempo seja pelo menos tão grande, e as arestas depois dele apenas acrescentam tempo, pois nenhuma tem peso negativo. Portanto, você define esse nó, relaxa suas arestas uma vez e repete o processo.
Um min-heap encontra o menor tempo. Quando o tempo de um nó melhora, insira uma nova entrada e deixe a antiga no lugar; uma entrada removida cujo tempo seja maior que dist está desatualizada, então você a ignora. Cada aresta insere no máximo uma entrada, portanto o heap contém no máximo E + 1 entradas e o custo total é O(E log E).
Algoritmo
- Defina
dist[k] = 0, todos os outros valores dedistcomo infinito e insira(0, k)em uma min-heap. - Remova o menor
(t, node); set > dist[node], ignore-o por estar desatualizado. - Para cada conexão
node → nextcom tempow, set + w < dist[next], definadist[next] = t + we insira(t + w, next). - Quando a heap estiver vazia, retorne -1 se algum
distfor infinito; caso contrário, retorne o maior valor.
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
Armadilhas e casos extremos
- Tratar as conexões como bidirecionais.
[3, 1, 2]transmite o sinal de 3 para 1 apenas, então o nó 3 nunca o recebe no segundo exemplo. - Usar uma busca em largura simples. Ela encontra a rota com o menor número de conexões: no primeiro exemplo, ela dá ao nó 2 o tempo 4 em vez de 3.
- Esquecer o -1. Encontrar o máximo sem uma verificação retorna infinito ou oculta o nó que nunca recebeu o sinal.
- Usar o maior int como infinito.
dist[u] + wentão transborda para um número negativo quandounão foi alcançado; ignore nós não alcançados ou use 10^9.
Perguntas frequentes3
Qual é a complexidade de tempo de Network Delay Time?
Com o algoritmo de Dijkstra e um heap binário, o tempo é O(E log E), em que E é o número de ligações. Isso equivale a O(E log n), já que E é no máximo n². O espaço é O(n + E). Bellman-Ford leva O(n · E) de tempo.
Por que o algoritmo de Dijkstra precisa de pesos não negativos?
Dijkstra nunca revisita um nó já estabelecido, o que só é seguro se nenhuma rota posterior puder ser mais curta. Com ligações A → B com tempo 2, A → C com tempo 3 e C → B com tempo -2, ele estabelece B com tempo 2, mas a rota passando por C chega a ele em 1. Bellman-Ford lida com tempos negativos.
Você consegue resolver o problema Network Delay Time sem um heap?
Sim. O Dijkstra com um array simples percorre todos os nós ainda não estabelecidos para encontrar o menor tempo, o que custa O(n²) no total. Ele é mais eficiente em grafos densos, nos quais E é próximo de n². Em grafos esparsos, como os de 3.000 nós e 4.000 conexões, a versão com heap faz bem menos trabalho.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def networkDelayTime(times, n, k):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Saída Esperada
4