Network Delay Time

Q: Qual é a complexidade de tempo do problema Network Delay Time?

Com o algoritmo de Dijkstra e um heap binário, a complexidade é O(E log E), em que E é o número de conexões. Isso é o mesmo que O(E log n), já que E é no máximo n². A lista de adjacência, os tempos e o heap ocupam O(n + E) espaço. O algoritmo de Bellman-Ford leva O(n · E) tempo e ocupa O(n) espaço.

Q: Por que o algoritmo de Dijkstra precisa de pesos não negativos?

Dijkstra confirma o nó com o menor tempo provisório e nunca mais o examina. Isso só é seguro se nenhuma rota posterior puder ser mais curta e, com pesos não negativos, toda rota que passe por um nó ainda não confirmado custa pelo menos o tempo desse nó. Um enlace negativo invalida o argumento: uma rota que passe por um nó que parecia mais caro ainda pode acabar sendo mais barata. Para pesos negativos, use Bellman-Ford.

Q: Por que não usar BFS para o tempo de atraso da rede?

A BFS visita os nós de acordo com a quantidade de conexões que os separam do início, o que corresponde à ordem de chegada somente quando cada conexão leva o mesmo tempo. Aqui, os tempos das conexões são diferentes, então uma rota com mais conexões pode chegar antes. Se todos os tempos fossem iguais, a BFS seria suficiente e, com tempos de apenas 0 e 1, uma BFS 0-1 baseada em deque funciona.

Q: Você consegue resolver Network Delay Time sem um heap?

Sim. O algoritmo de Dijkstra com um array simples percorre todos os nós não definidos para encontrar o menor tempo, o que custa O(n²) no total e não precisa de heap. Essa é a melhor opção em grafos densos, nos quais E é próximo de n². Em grafos esparsos, como os testes grandes aqui, com 3,000 nós e 4,000 conexões, a versão com heap faz bem menos trabalho.

MédioCaminhos mínimos Grafos Heap

+10

Uma rede tem n nós, rotulados de 1 a n. Você recebe suas conexões em uma lista times, na qual times[i] = [u, v, w] significa que um sinal enviado do nó u chega ao nó v após w unidades de tempo. As conexões funcionam em apenas uma direção.

Um sinal sai do nó k no instante 0 e percorre todas as conexões que conseguir. Retorne o instante em que o último nó o recebe ou -1 se algum nó nunca o receber.

Função

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

timesinteger-2d-array: os links direcionados, cada um 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 ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n e u ≠ v
0 ≤ w ≤ 100
Nenhum par de links compartilha os mesmos valores de u e v.
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 nó 3 ouve o sinal no instante 1. O nó 2 poderia ouvi-lo no instante 4 pelo link direto, mas a rota pelo nó 3 chega em 1 + 2 = 3, e o nó 4 o ouve em 3 + 1 = 4. O nó 4 é o último, no instante 4.

+16 testes ocultos ao enviar

Para ir além

Suponha que o sinal desapareça após 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.

0 de 3 abertas

Solução

Cada nó recebe o sinal após o tempo correspondente à duração de sua rota mais rápida a partir de k, então a tarefa consiste em encontrar os caminhos mínimos de uma única origem em um grafo direcionado e, em seguida, obter o máximo. A resposta é o maior tempo mínimo ou -1 quando algum nó não tem uma rota. Os tempos dos enlaces nunca são negativos, o que permite que o algoritmo de Dijkstra finalize cada nó uma única vez, na ordem de chegada, usando um min-heap. Abaixo, E é o número de enlaces, times.length.

Busca em profundidade que revisita a cada rota mais rápida

Correta, mas não termina nos maiores testes

Intuição

Comece uma busca no nó k com o tempo 0 e siga cada link, levando consigo o tempo decorrido. Registre, para cada nó, a chegada mais rápida encontrada. Quando a busca chegar a um nó em um tempo igual ou posterior ao registrado, pare ali: tudo o que essa rota poderia oferecer mais adiante já foi oferecido pela rota mais rápida. Quando chegar ao nó em menos tempo, o registro melhora, e tudo o que estiver depois do nó também pode melhorar, então a busca continua a partir dele.

Isso está sempre correto. A busca só para quando nenhuma rota melhora qualquer registro, e a rota mais rápida até cada nó melhora o registro desse nó em algum momento, então cada registro termina com o tempo realmente mais rápido.

O problema é quantas vezes um nó pode melhorar. Uma busca em profundidade segue o primeiro link que encontra até o fim, então pode chegar a um nó por uma rota lenta, depois por uma um pouco mais rápida e, em seguida, por outra ainda mais rápida, percorrendo tudo o que estiver depois do nó a cada vez. Imagine 18 portões em fila. Entre cada par de portões, você pode pegar um link gratuito ou um desvio, uma cadeia de links cujos tempos somam 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, cada um menor que o anterior, e percorre os 1,700 nós depois dele todas as vezes: cerca de 220 milhões de etapas. Dois dos testes grandes são construídos dessa forma, um com cada desvio listado antes do link gratuito e outro com ele listado depois, então uma busca tropeça em um deles, qualquer que seja a ordem em que tente os links.

Algoritmo

Crie uma lista de adjacência: para cada nó, os links que saem dele e seus tempos.
Defina o melhor tempo de cada nó como infinito e empilhe (k, 0).
Retire (node, t) da pilha. Se t não for menor que best[node], ignore-o; caso contrário, defina best[node] = t.
Empilhe (next, t + w) para cada link de node cuja chegada seja anterior a best[next].
Quando a pilha estiver vazia, retorne -1 se algum melhor tempo ainda for infinito; caso contrário, retorne o maior deles.

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: relaxe cada aresta até n-1 vezes

Intuição

Mantenha um tempo provisório dist para cada nó: 0 para k e infinito para os demais. Relaxar uma ligação u → v com tempo w significa: se dist[u] + w for menor que dist[v], a ligação oferece um caminho mais rápido até v, então reduza dist[v] para esse valor. Bellman-Ford percorre a lista inteira em várias passagens e relaxa cada ligação em cada passagem.

Por que isso termina com os tempos corretos? Considere o caminho mais rápido até algum nó, digamos k → a → b → v. A primeira passagem relaxa k → a enquanto dist[k] já é 0, então, depois dela, dist[a] é definitivo. A segunda passagem torna dist[b] definitivo, e a terceira, dist[v]. Um caminho mais rápido nunca precisa visitar um nó duas vezes, já que um ciclo nunca leva um tempo negativo, portanto tem no máximo n-1 ligações, e n-1 passagens determinam o tempo de todos os nós. Uma passagem que não altera nada prova que nenhuma passagem posterior poderá alterar algo, então você pode parar nesse ponto.

Cada passagem custa O(E), então o pior caso é O(n · E). A ordem da lista determina o quanto isso pode piorar: se as ligações de um caminho longo forem listadas da extremidade mais distante de volta ao início, cada passagem determina o tempo de mais um nó. Um teste grande é exatamente esse caso: uma cadeia de 3,000 nós listada ao contrário, que exige 2,999 passagens sobre 4,000 ligações: cerca de 12 milhões de relaxamentos. Isso ainda é executado em tempo hábil nesse tamanho, mas o trabalho cresce com n vezes E. A força do Bellman-Ford está em outro aspecto: ele continua correto quando os tempos de algumas ligações são negativos, situação em que Dijkstra falha.

Algoritmo

Defina dist[k] = 0 e todos os outros valores de dist como infinito.
Repita até n-1 vezes: para cada ligação [u, v, w], se dist[u] + w < dist[v], defina dist[v] = dist[u] + w.
Encerre antes se uma passagem não alterar nada.
Retorne -1 se algum valor de dist ainda for infinito; caso contrário, retorne 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 worst

Algoritmo de Dijkstra com uma heap mínima

Intuição

O Bellman-Ford desperdiça passagens porque relaxa as conexões que saem de nós cujos tempos ainda não são definitivos e precisa voltar a eles. O algoritmo de Dijkstra relaxa as conexões de cada nó exatamente uma vez, no momento em que seu tempo se torna definitivo. A questão é como saber quando isso acontece.

A resposta é uma regra gulosa: entre os nós ainda não definidos, aquele com o menor tempo provisório já tem seu tempo definitivo. Qualquer outro caminho até ele precisa sair dos nós definidos em algum momento, passando por um nó ainda não definido cujo tempo seja pelo menos tão grande, e as conexões seguintes só podem acrescentar tempo, porque nenhuma tem peso negativo. Então, você define esse nó, relaxa suas conexões e repete. No primeiro exemplo, o nó 1 tem seu tempo definido como 0 e oferece ao nó 2 o tempo 4 e ao nó 3 o tempo 1. O nó 3 tem o menor tempo, passa a ter seu tempo definido como 1 e reduz o tempo do nó 2 para 3. O nó 2 passa a ter seu tempo definido como 3 e oferece ao nó 4 o tempo 4, que tem seu tempo definido por último. A resposta é 4.

Um min-heap encontra rapidamente o menor tempo provisório. Insira (time, node) sempre que o tempo de um nó melhorar e deixe a entrada mais antiga no heap, em vez de procurá-la. Quando a entrada mais antiga sair mais tarde, seu tempo será maior que o tempo atual do nó, então você a ignora. Cada conexão insere no máximo uma entrada, portanto o heap nunca contém mais de E + 1 entradas, e cada inserção ou remoção custa O(log E). Isso resulta em O(E log E) no total, com espaço O(n + E) para a lista de adjacência, os tempos e o heap.

Tempos não negativos são o que torna segura a regra gulosa. Considere as conexões A → B com tempo 2, A → C com tempo 3 e C → B com tempo -2. Dijkstra define o tempo de B como 2, mas o caminho por C chega até ele em 1. Um sinal nunca pode chegar antes de ser enviado, então todo tempo aqui é pelo menos 0 e a regra se aplica.

Algoritmo

Crie uma lista de adjacência de pares (next, w) para cada nó.
Defina dist[k] = 0, todos os outros valores de dist como infinito e coloque (0, k) em uma min-heap.
Remova o menor (t, node). Se t > dist[node], a entrada está desatualizada: ignore-a.
Caso contrário, t é definitivo. Para cada aresta de node a next com tempo w, se t + w < dist[next], defina dist[next] = t + w e coloque (t + w, next) na heap.
Quando a heap estiver vazia, retorne -1 se algum valor de dist for 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

A maioria dos bugs ignora a direção dos enlaces, confia no primeiro tempo oferecido a um nó ou perde de vista os nós que nunca recebem o sinal.

Tratar os enlaces como bidirecionais. [3, 1, 2] leva o sinal de 3 para 1 apenas, e é por isso que o nó 3 nunca o recebe no segundo exemplo.
Usar uma busca em largura simples. Ela encontra a rota com menos enlaces, não a mais rápida: no primeiro exemplo, atribui ao nó 2 o tempo 4 pelo enlace direto, em vez de 3 passando pelo nó 3.
Marcar um nó como definitivo quando ele é inserido, em vez de quando é removido. O primeiro tempo oferecido a um nó nem sempre é o melhor; somente a menor entrada removida da heap é definitiva.
Esquecer o -1. Obter o máximo sem verificar os casos retorna infinito ou informa o maior tempo finito e oculta o nó que nunca recebeu o sinal.
Contar os nós a partir de 0. Os nós são rotulados de 1 a n, então dimensione os arrays como n+1 e exclua do máximo o espaço não utilizado 0.
Estouro causado pelo infinito. Se infinito for o maior int, dist[u] + w dá a volta e se torna um número negativo para um u não alcançado. Ignore os nós não alcançados ou use um valor como 10^9, que deixa uma margem.

Perguntas frequentes4

Qual é a complexidade de tempo do problema Network Delay Time?

Com o algoritmo de Dijkstra e um heap binário, a complexidade é O(E log E), em que E é o número de conexões. Isso é o mesmo que O(E log n), já que E é no máximo n². A lista de adjacência, os tempos e o heap ocupam O(n + E) espaço. O algoritmo de Bellman-Ford leva O(n · E) tempo e ocupa O(n) espaço.

Por que o algoritmo de Dijkstra precisa de pesos não negativos?

Dijkstra confirma o nó com o menor tempo provisório e nunca mais o examina. Isso só é seguro se nenhuma rota posterior puder ser mais curta e, com pesos não negativos, toda rota que passe por um nó ainda não confirmado custa pelo menos o tempo desse nó. Um enlace negativo invalida o argumento: uma rota que passe por um nó que parecia mais caro ainda pode acabar sendo mais barata. Para pesos negativos, use Bellman-Ford.

Por que não usar BFS para o tempo de atraso da rede?

A BFS visita os nós de acordo com a quantidade de conexões que os separam do início, o que corresponde à ordem de chegada somente quando cada conexão leva o mesmo tempo. Aqui, os tempos das conexões são diferentes, então uma rota com mais conexões pode chegar antes. Se todos os tempos fossem iguais, a BFS seria suficiente e, com tempos de apenas 0 e 1, uma BFS 0-1 baseada em deque funciona.

Você consegue resolver Network Delay Time sem um heap?

Sim. O algoritmo de Dijkstra com um array simples percorre todos os nós não definidos para encontrar o menor tempo, o que custa O(n²) no total e não precisa de heap. Essa é a melhor opção em grafos densos, nos quais E é próximo de n². Em grafos esparsos, como os testes grandes aqui, com 3,000 nós e 4,000 conexões, a versão com heap faz bem menos trabalho.

Python

def networkDelayTime(times, n, k):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

Network Delay Time

Função

Restrições

Exemplos

Dicas

Solução

Busca em profundidade que revisita a cada rota mais rápida

Bellman-Ford: relaxe cada aresta até n-1 vezes

Algoritmo de Dijkstra com uma heap mínima

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos