Network Delay Time

Q: ¿Cuál es la complejidad temporal de Network Delay Time?

Con el algoritmo de Dijkstra y un montículo binario, es O(E log E), donde E es el número de enlaces. Eso equivale a O(E log n), ya que E es como máximo n². La lista de adyacencia, los tiempos y el montículo ocupan O(n + E) espacio. Bellman-Ford tarda O(n · E) y ocupa O(n) espacio.

Q: ¿Por qué el algoritmo de Dijkstra necesita pesos no negativos?

Dijkstra establece el nodo con el menor tiempo provisional y nunca vuelve a examinarlo. Esto solo es seguro si ninguna ruta posterior puede ser más corta y, con pesos no negativos, toda ruta que pase por un nodo no establecido cuesta al menos lo mismo que el tiempo de ese nodo. Un enlace negativo rompe el argumento: una ruta que pase por un nodo que parecía más costoso aún puede acabar siendo más barata. Para pesos negativos, usa Bellman-Ford.

Q: ¿Por qué no usar BFS para el tiempo de retardo de la red?

BFS visita los nodos según la cantidad de enlaces que los separan del inicio, lo que coincide con el orden de llegada solo cuando todos los enlaces tardan lo mismo. Aquí los tiempos de los enlaces difieren, por lo que una ruta con más enlaces puede llegar antes. Si todos los tiempos fueran iguales, BFS sería suficiente, y si los tiempos fueran solo 0 y 1, funcionaría un BFS 0-1 basado en una deque.

Q: ¿Puedes resolver Network Delay Time sin un montículo?

Sí. Dijkstra con un arreglo simple recorre todos los nodos cuyo tiempo aún no se ha establecido para encontrar el menor, lo que cuesta O(n²) en total y no necesita un montículo. Esa es la mejor opción en grafos densos, donde E se acerca a n². En grafos dispersos, como las pruebas grandes de aquí, con 3,000 nodos y 4,000 enlaces, la versión con montículo realiza mucho menos trabajo.

MedioCaminos más cortos Grafos Montículo

+10

Una red tiene n nodos, etiquetados del 1 al n. Recibes sus enlaces como una lista times, donde times[i] = [u, v, w] significa que una señal enviada desde el nodo u llega al nodo v después de w unidades de tiempo. Los enlaces funcionan en una sola dirección.

Una señal sale del nodo k en el instante 0 y viaja por todos los enlaces que puede. Devuelve el instante en que la recibe el último nodo, o -1 si algún nodo nunca la recibe.

Función

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

timesinteger-2d-array: los enlaces dirigidos, cada uno como [u, v, w]
ninteger: el número de nodos
kinteger: el nodo que envía la señal
Devuelveinteger: el momento en que el último nodo recibe la señal, o -1

Restricciones

2 ≤ n ≤ 3000
1 ≤ times.length ≤ 4000
times[i].length = 3
1 ≤ u, v ≤ n y u ≠ v
0 ≤ w ≤ 100
Ningún par de enlaces comparte los mismos u y v.
1 ≤ k ≤ n

Ejemplos

Entrada: times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
Salida: 4
Explicación: El nodo 3 recibe la señal en el instante 1. El nodo 2 podría recibirla en el instante 4 a través de su conexión directa, pero la ruta a través del nodo 3 llega en 1 + 2 = 3, y el nodo 4 la recibe en 3 + 1 = 4. El nodo 4 es el último, en el instante 4.

+16 pruebas ocultas al enviar

Para ir más allá

Supón que la señal se debilita después de atravesar m enlaces. ¿Cómo encuentras el momento en que el último nodo la oye dentro de ese límite?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada nodo recibe la señal en el tiempo que tarda su ruta más rápida desde k, así que la tarea consiste en hallar las rutas más cortas desde un único origen en un grafo dirigido y, después, obtener el máximo. La respuesta es el mayor tiempo de ruta más corta, o -1 si algún nodo no tiene ruta. Los tiempos de los enlaces nunca son negativos, lo que permite que el algoritmo de Dijkstra dé por definitivos los nodos una sola vez, en orden de llegada, usando un montículo mínimo. A continuación, E es la cantidad de enlaces, times.length.

Búsqueda en profundidad que vuelve a visitar cada ruta más rápida

Correcto, pero no termina con las pruebas más grandes

Intuición

Inicia una búsqueda en el nodo k con tiempo 0 y sigue todos los enlaces, llevando el tiempo acumulado. Registra, para cada nodo, el tiempo de llegada más rápido observado. Cuando la búsqueda llega a un nodo en un tiempo igual o posterior al de su registro, se detiene allí: cualquier cosa que esa ruta pudiera ofrecer más adelante ya la ofreció la ruta más rápida. Cuando llega al nodo antes, el registro mejora y todo lo que hay detrás del nodo también podría mejorar, así que la búsqueda continúa desde allí.

Esto siempre es correcto. La búsqueda solo se detiene cuando ninguna ruta mejora ningún registro, y la ruta más rápida a cada nodo mejora el registro de ese nodo en algún momento, así que cada registro termina con el tiempo verdaderamente más rápido.

El problema es cuántas veces puede mejorar un nodo. Una búsqueda en profundidad sigue el primer enlace que encuentra hasta el final, así que puede llegar a un nodo por una ruta lenta, luego por otra un poco más rápida y después por una aún más rápida, recorriendo cada vez todo lo que hay detrás del nodo. Imagina 18 compuertas en fila. Entre cada par de compuertas puedes tomar un enlace gratuito o un desvío, una cadena de enlaces cuyos tiempos suman 65,536, 32,768 y así sucesivamente hasta llegar a 1. Al probar primero los desvíos, la búsqueda llega a la última compuerta en 131,072 tiempos distintos, cada uno más rápido que el anterior, y recorre los 1,700 nodos que hay detrás de ella cada vez: unos 220 millones de pasos. Dos de las pruebas grandes están construidas de esta manera: en una, cada desvío aparece antes que su enlace gratuito y, en la otra, aparece después; así, la búsqueda cae en una de ellas sin importar en qué orden pruebe los enlaces.

Algoritmo

Construye una lista de adyacencia: para cada nodo, los enlaces que salen de él con sus tiempos.
Establece el mejor tiempo de cada nodo en infinito y apila (k, 0).
Desapila (node, t). Si t no es menor que best[node], omítelo; de lo contrario, establece best[node] = t.
Apila (next, t + w) por cada enlace desde node cuya llegada sea anterior a best[next].
Cuando la pila esté vacía, devuelve -1 si algún mejor tiempo sigue siendo infinito; de lo contrario, devuelve el mayor.

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: relaja cada enlace hasta n-1 veces

Intuición

Mantén un tiempo provisional dist para cada nodo: 0 para k e infinito para el resto. Relajar un enlace u → v con tiempo w significa: si dist[u] + w es menor que dist[v], el enlace ofrece una forma más rápida de llegar a v, así que reduce dist[v] a ese valor. Bellman-Ford hace pasadas por toda la lista y relaja cada enlace en cada pasada.

¿Por qué al final se obtienen los tiempos correctos? Toma la ruta más rápida hasta algún nodo, por ejemplo, k → a → b → v. La primera pasada relaja k → a mientras dist[k] ya es 0, así que al terminar dist[a] es definitivo. La segunda pasada hace que dist[b] sea definitivo, y la tercera, dist[v]. Una ruta más rápida nunca necesita visitar un nodo dos veces, porque un ciclo nunca requiere un tiempo negativo; por lo tanto, tiene como máximo n-1 enlaces, y n-1 pasadas establecen el valor de cada nodo. Una pasada que no cambia nada demuestra que ninguna pasada posterior podrá hacerlo, así que te detienes ahí.

Cada pasada cuesta O(E), así que el peor caso es O(n · E). El orden de la lista determina cuánto se complica: si los enlaces de una ruta larga aparecen listados desde el extremo más lejano hasta el inicio, cada pasada establece el valor de un nodo más. Una prueba grande consiste precisamente en eso: una cadena de 3,000 nodos listada en orden inverso, que requiere 2,999 pasadas sobre 4,000 enlaces: unos 12 millones de relajaciones. Aun así, se ejecuta a tiempo con este tamaño, pero el trabajo crece en función de n por E. La ventaja de Bellman-Ford está en otra parte: sigue siendo correcto cuando algunos tiempos de enlace son negativos, situación en la que Dijkstra falla.

Algoritmo

Establece dist[k] = 0 y todos los demás valores de dist en infinito.
Repite hasta n-1 veces: para cada enlace [u, v, w], si dist[u] + w < dist[v], establece dist[v] = dist[u] + w.
Detente antes si hay una pasada que no cambia nada.
Devuelve -1 si algún valor de dist sigue siendo infinito; de lo contrario, devuelve el mayor.

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 con un montículo mínimo

Intuición

Bellman-Ford desperdicia pasadas porque relaja los enlaces que salen de nodos cuyos tiempos aún no son definitivos, y tiene que volver a ellos. El algoritmo de Dijkstra relaja los enlaces de cada nodo exactamente una vez, en el momento en que su tiempo es definitivo. La pregunta es cómo saber cuándo ocurre eso.

La respuesta es una regla codiciosa: entre los nodos que aún no se han fijado, el que tiene el menor tiempo tentativo ya tiene un tiempo definitivo. Cualquier otra ruta hasta él debe salir de los nodos fijados en algún momento, pasando por un nodo sin fijar cuyo tiempo sea al menos igual, y los enlaces posteriores solo pueden sumar tiempo, porque ninguno es negativo. Así que fijas ese nodo, relajas sus enlaces y repites. En el primer ejemplo, el nodo 1 se fija en 0 y ofrece al nodo 2 el tiempo 4 y al nodo 3 el tiempo 1. El nodo 3 es el menor, se fija en 1 y reduce el tiempo del nodo 2 a 3. El nodo 2 se fija en 3 y ofrece al nodo 4 el tiempo 4, que se fija al final. La respuesta es 4.

Un montículo mínimo encuentra rápidamente el menor tiempo tentativo. Inserta (time, node) cada vez que mejora el tiempo de un nodo, y deja la entrada anterior en el montículo en lugar de buscarla. Cuando la entrada anterior sale más tarde, su tiempo es mayor que el tiempo actual del nodo, así que la omites. Cada enlace inserta como máximo una entrada, por lo que el montículo nunca contiene más de E + 1 entradas, y cada inserción o extracción cuesta O(log E). Eso da un costo total de O(E log E), con un espacio de O(n + E) para la lista de adyacencia, los tiempos y el montículo.

Los tiempos no negativos son lo que hace segura la regla codiciosa. Considera los enlaces A → B con tiempo 2, A → C con tiempo 3 y C → B con tiempo -2. Dijkstra fija B en 2, pero la ruta que pasa por C llega a él en 1. Una señal nunca puede llegar antes de ser enviada, así que todos los tiempos aquí son al menos 0 y la regla se cumple.

Algoritmo

Construye una lista de adyacencia de pares (next, w) para cada nodo.
Establece dist[k] = 0, asigna infinito a todos los demás dist y agrega (0, k) a un montículo mínimo.
Extrae el menor (t, node). Si t > dist[node], la entrada está obsoleta: omítela.
De lo contrario, t es definitivo. Para cada enlace desde node hasta next con tiempo w, si t + w < dist[next], establece dist[next] = t + w y agrega (t + w, next).
Cuando el montículo esté vacío, devuelve -1 si algún dist es infinito; de lo contrario, devuelve el mayor.

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

Errores comunes y casos límite

La mayoría de los errores ignoran la dirección de los enlaces, confían en el primer tiempo ofrecido a un nodo o pierden de vista los nodos a los que nunca llega la señal.

Tratar los enlaces como bidireccionales. [3, 1, 2] lleva la señal de 3 a 1 únicamente, por lo que el nodo 3 nunca la recibe en el segundo ejemplo.
Usar una búsqueda en anchura simple. Encuentra la ruta con menos enlaces, no la más rápida: en el primer ejemplo, asigna al nodo 2 un tiempo de 4 por el enlace directo en lugar de 3 pasando por el nodo 3.
Marcar un nodo como definitivo cuando se inserta en vez de cuando se extrae. El primer tiempo ofrecido a un nodo no siempre es el mejor; solo la entrada más pequeña extraída del montículo es definitiva.
Olvidar el -1. Tomar el máximo sin comprobarlo puede devolver infinito o indicar el mayor tiempo finito y ocultar el nodo que nunca recibió la señal.
Contar los nodos desde 0. Los nodos están etiquetados del 1 al n, así que dimensiona los arreglos con n+1 y excluye del máximo la posición 0, que no se usa.
Desbordamiento de infinito. Si infinito es el int más grande, dist[u] + w se desborda y se convierte en un número negativo para un u no alcanzado. Omite los nodos no alcanzados o usa un valor como 10^9 que deje margen.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Network Delay Time?

Con el algoritmo de Dijkstra y un montículo binario, es O(E log E), donde E es el número de enlaces. Eso equivale a O(E log n), ya que E es como máximo n². La lista de adyacencia, los tiempos y el montículo ocupan O(n + E) espacio. Bellman-Ford tarda O(n · E) y ocupa O(n) espacio.

¿Por qué el algoritmo de Dijkstra necesita pesos no negativos?

Dijkstra establece el nodo con el menor tiempo provisional y nunca vuelve a examinarlo. Esto solo es seguro si ninguna ruta posterior puede ser más corta y, con pesos no negativos, toda ruta que pase por un nodo no establecido cuesta al menos lo mismo que el tiempo de ese nodo. Un enlace negativo rompe el argumento: una ruta que pase por un nodo que parecía más costoso aún puede acabar siendo más barata. Para pesos negativos, usa Bellman-Ford.

¿Por qué no usar BFS para el tiempo de retardo de la red?

BFS visita los nodos según la cantidad de enlaces que los separan del inicio, lo que coincide con el orden de llegada solo cuando todos los enlaces tardan lo mismo. Aquí los tiempos de los enlaces difieren, por lo que una ruta con más enlaces puede llegar antes. Si todos los tiempos fueran iguales, BFS sería suficiente, y si los tiempos fueran solo 0 y 1, funcionaría un BFS 0-1 basado en una deque.

¿Puedes resolver Network Delay Time sin un montículo?

Sí. Dijkstra con un arreglo simple recorre todos los nodos cuyo tiempo aún no se ha establecido para encontrar el menor, lo que cuesta O(n²) en total y no necesita un montículo. Esa es la mejor opción en grafos densos, donde E se acerca a n². En grafos dispersos, como las pruebas grandes de aquí, con 3,000 nodos y 4,000 enlaces, la versión con montículo realiza mucho menos trabajo.

Python

def networkDelayTime(times, n, k):
    # Escribe el código aquí

Casos de prueba

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

Función

Restricciones

Ejemplos

Pistas

Solución

Búsqueda en profundidad que vuelve a visitar cada ruta más rápida

Bellman-Ford: relaja cada enlace hasta n-1 veces

Algoritmo de Dijkstra con un montículo mínimo

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares