Network Delay Time
Una red tiene n nodos etiquetados del 1 al n. El enlace times[i] = [u, v, w] transporta una señal del nodo u al nodo v en w unidades de tiempo, solo en esa dirección.
Una señal sale del nodo k en el tiempo 0 y viaja por todos los enlaces que puede. Devuelve el tiempo en que la recibe el último nodo, o -1 si hay algún nodo que nunca la recibe.
Función
- 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 ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ nyu ≠ v0 ≤ w ≤ 100- No hay dos enlaces que compartan tanto el mismo
ucomo el mismov. 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 enlace directo llega al nodo 2 en el tiempo 4, pero la ruta a través del nodo 3 llega en 1 + 2 = 3. El nodo 4 recibe la señal al final, en 3 + 1 = 4.
- Entrada
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- Salida
- -1
- Explicación
- El nodo 2 recibe la señal en el instante 3, pero el único enlace que llega al nodo 3 va del 3 al 1. El nodo 3 nunca la recibe, así que la respuesta es -1.
- Entrada
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- Salida
- 2
- Explicación
- El enlace al nodo 3 tarda 0, así que el nodo 3 recibe la señal en el instante 0. Después, el nodo 1 la recibe en 0 + 2 = 2, antes que los 5 de su enlace directo.
Para ir más allá
Supón que la señal se desvanece después de cruzar m enlaces. ¿Cómo encuentras el tiempo 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.
Un nodo recibe la señal en el tiempo que tarda la ruta más rápida en llegar a él desde
k. Así que la respuesta es el mayor de esos tiempos más rápidos, o -1 si algún nodo no tiene ninguna ruta.Ningún enlace requiere un tiempo negativo. Así que, entre los nodos cuyo tiempo aún no es definitivo, el que tiene el menor tiempo provisional no puede llegar más rápido: cualquier otra ruta hacia él pasa por otro de esos nodos, al que se llega igual o más tarde. Fija los nodos en orden de llegada.
Mantén un montículo mínimo de pares
(time, node). Extrae el menor, omítelo si el nodo ya tiene un tiempo menor y añade cada vecino cuyo tiempo mejore. Cuando el montículo esté vacío, toma el tiempo más grande.
Solución
Cada nodo recibe la señal en un tiempo igual a la longitud de su ruta más rápida desde k, así que se trata de encontrar los caminos más cortos desde un único origen y luego calcular el máximo, o devolver -1 si un nodo no tiene ruta. Los tiempos de los enlaces nunca son negativos, así que el algoritmo de Dijkstra finaliza cada nodo una sola vez. A continuación, E es 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
Busca en profundidad a partir de k, llevando el tiempo acumulado y registrando la llegada más rápida a cada nodo. Una ruta que llega a un nodo en un tiempo igual o posterior al de su registro se detiene; una que llega antes mejora el registro y continúa la búsqueda. Cada registro acaba reflejando el tiempo verdaderamente más rápido, porque la ruta más rápida lo mejora en algún momento.
Un nodo puede mejorar muchas veces. Coloca 18 puertas seguidas, con cada par unido por un enlace gratuito y por un desvío de 65,536, 32,768 y así sucesivamente hasta llegar a 1. Si se prueban primero los desvíos, la búsqueda llega a la última puerta en 131,072 tiempos distintos y recorre todo lo que hay detrás cada vez: el trabajo es exponencial en n.
Algoritmo
- Establece todos los mejores tiempos en infinito y apila
(k, 0). - Desapila
(node, t). Omítelo a menos quet < best[node]; después establecebest[node] = t. - Apila
(next, t + w)por cada enlace desdenodecuya llegada mejorebest[next]. - Cuando la pila esté vacía, devuelve -1 si algún mejor tiempo es 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 worstBellman-Ford: relaja cada enlace hasta n-1 veces
Intuición
Mantén un tiempo provisional dist por nodo, 0 para k. Al relajar un enlace u → v, se reduce dist[v] a dist[u] + w si ese valor es menor. Bellman-Ford relaja todos los enlaces en cada pasada.
Toma la ruta más rápida hasta un nodo, por ejemplo k → a → b → v. La primera pasada fija dist[a], la segunda dist[b] y la tercera dist[v]. Una ruta más rápida nunca repite un nodo, así que tiene como máximo n-1 enlaces, y n-1 pasadas fijan todos los nodos.
Cada pasada cuesta O(E). Una cadena de 3,000 nodos listada desde el extremo más lejano hacia atrás requiere 2,999 pasadas sobre 4,000 enlaces: unos 12 millones de relajaciones.
Algoritmo
- Establece
dist[k] = 0y asigna infinito a cada uno de los demásdist. - Repite hasta n-1 veces: para cada enlace
[u, v, w], sidist[u] + w < dist[v], establecedist[v] = dist[u] + w. - Detente antes si una pasada no cambia nada.
- Devuelve -1 si algún
distsigue 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 worstAlgoritmo de Dijkstra con un montículo mínimo
Intuición
Entre los nodos que aún no se han asentado, el que tiene el menor tiempo provisional ya es definitivo. Cualquier otra ruta hasta él debe salir de los nodos asentados pasando por un nodo no asentado cuyo tiempo sea al menos igual, y los enlaces posteriores solo suman tiempo, porque ninguno es negativo. Así que asientas ese nodo, relajas sus enlaces una vez y repites.
Un montículo mínimo encuentra el menor tiempo. Cuando mejora un nodo, insertas una nueva entrada y dejas la antigua en su sitio; una entrada extraída cuyo tiempo es mayor que dist está obsoleta, así que la omites. Cada enlace inserta como máximo una entrada, por lo que el montículo contiene como máximo E + 1 entradas y el total es O(E log E).
Algoritmo
- Establece
dist[k] = 0, cada uno de los demás valores dedisten infinito y agrega(0, k)a un montículo mínimo. - Extrae el menor
(t, node); sit > dist[node], omítelo porque está obsoleto. - Para cada enlace
node → nextcon tiempow, sit + w < dist[next], establecedist[next] = t + wy agrega(t + w, next). - Cuando el montículo esté vacío, devuelve -1 si algún valor de
distes 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
- Tratar los enlaces como bidireccionales.
[3, 1, 2]lleva la señal solo de 3 a 1, así que el nodo 3 nunca la recibe en el segundo ejemplo. - Usar una búsqueda en anchura simple. Encuentra la ruta con menos enlaces: en el primer ejemplo, asigna al nodo 2 el tiempo 4 en lugar de 3.
- Olvidar el -1. Tomar el máximo sin comprobarlo devuelve infinito u oculta el nodo que nunca recibió la señal.
- Usar el entero más grande como infinito.
dist[u] + wdespués se desborda y se convierte en un número negativo para ununo alcanzado; omite los nodos no alcanzados o usa 10^9.
Preguntas frecuentes3
¿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². El espacio es O(n + E). Bellman-Ford tarda O(n · E).
¿Por qué el algoritmo de Dijkstra necesita pesos no negativos?
Dijkstra nunca vuelve a visitar un nodo ya establecido, lo cual es seguro solo si ninguna ruta posterior puede ser más corta. Con enlaces A → B de tiempo 2, A → C de tiempo 3 y C → B de tiempo -2, establece B en 2, pero la ruta a través de C llega a él en 1. Bellman-Ford maneja los tiempos negativos.
¿Puedes resolver el problema «Network Delay Time» sin un montículo?
Sí. Dijkstra con un arreglo simple recorre cada nodo no resuelto para encontrar el menor tiempo, lo que cuesta O(n²) en total. Es más eficiente en grafos densos, donde E se acerca a n². En grafos dispersos, como los de 3.000 nodos y 4.000 enlaces, la versión con heap realiza mucho menos trabajo.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def networkDelayTime(times, n, k):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
Salida Esperada
4