Network Delay Time y reconstrucción de caminos
Resuelva network-delay-time con Dijkstra, reconstruya el camino mínimo real mediante un mapa de predecesores y analice BFS bidireccional para grafos grandes.
Network Delay Time y reconstrucción de caminos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Problema Network Delay Time
Network Delay Time (LeetCode 743): dada una red de n nodos y aristas dirigidas ponderadas que representan los tiempos de propagación de la señal, encuentre el tiempo mínimo que tarda una señal enviada desde el nodo k en llegar a todos los nodos. Si algún nodo no es alcanzable, devuelva -1. Esta es una aplicación directa de Dijkstra: la respuesta es la distancia más corta máxima desde k entre todos los nodos.
Solución: Dijkstra + máximo de las distancias
Ejecute Dijkstra desde el origen k para encontrar dist[v] para todos los nodos v. La respuesta es max(dist.values()). Si algún dist[v] sigue siendo inf, ese nodo no es alcanzable: devuelva -1. La señal recorre todas las rutas simultáneamente, por lo que el cuello de botella es el nodo al que se tarda más en llegar.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Reconstrucción de rutas con el arreglo prev
Para reconstruir la ruta más corta real mientras calcula las distancias, mantenga un diccionario prev que registre el mejor predecesor de cada nodo. Cada vez que actualice dist[v], establezca prev[v] = u. Después de que Dijkstra termine, retroceda desde el destino siguiendo los punteros de prev hasta llegar al origen y, a continuación, invierta la ruta para obtenerla en el sentido de avance.
import heapq
from collections import defaultdict
def shortest_path_with_reconstruction(times, n, src, dst):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
prev = {i: None for i in range(1, n+1)}
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct path from src to dst
path, node = [], dst
while node is not None:
path.append(node)
node = prev[node]
return dist[dst], path[::-1]BFS bidireccional para grafos no ponderados grandes
Para grafos no ponderados grandes en los que solo se necesita un par de origen y destino, el BFS bidireccional puede ser significativamente más rápido que el BFS estándar. Ejecuta simultáneamente un BFS desde el origen y otro desde el destino, y se detiene cuando ambas fronteras se encuentran. La aceleración práctica es importante porque cada frontera solo necesita explorar la mitad de la profundidad del grafo, lo que reduce los nodos explorados de O(b^d) a O(2 × b^(d/2)), donde b es el factor de ramificación.
from collections import deque
def bidir_bfs(graph, src, dst):
if src == dst: return 0
front_q = deque([src]); front_visited = {src: 0}
back_q = deque([dst]); back_visited = {dst: 0}
def expand(queue, visited, other_visited):
node = queue.popleft()
for nxt in graph[node]:
if nxt not in visited:
visited[nxt] = visited[node] + 1
queue.append(nxt)
if nxt in other_visited:
return visited[nxt] + other_visited[nxt]
return -1
while front_q or back_q:
res = expand(front_q, front_visited, back_visited)
if res != -1: return res
res = expand(back_q, back_visited, front_visited)
if res != -1: return res
return -1Cuándo elegir cada algoritmo
Guía de decisión: grafo no ponderado, un solo par → BFS o BFS bidireccional. Grafo ponderado, pesos no negativos, un solo origen → Dijkstra. Grafo ponderado, posiblemente con pesos negativos, un solo origen → Bellman-Ford. Todos los pares → Floyd-Warshall (V pequeño) o V × Dijkstra (grafo disperso). Número de saltos restringido → Bellman-Ford modificado con pasadas limitadas. Expresar en voz alta esta justificación de la decisión durante las entrevistas demuestra madurez algorítmica.
Encuentre la ciudad con menos vecinos alcanzables (LeetCode 1334)
Dadas varias ciudades con rutas ponderadas y un distanceThreshold, encuentre la ciudad a la que se puede llegar desde el menor número de otras ciudades dentro del umbral (en caso de empate, prefiera el índice de ciudad mayor). Solución: calcule las rutas más cortas entre todos los pares con Floyd-Warshall y, después, cuente para cada ciudad cuántas otras ciudades son alcanzables dentro del umbral. Devuelva la ciudad con el recuento mínimo (en caso de empate: el índice máximo).
def findTheCity(n, edges, distanceThreshold):
INF = float('inf')
dist = [[INF]*n for _ in range(n)]
for i in range(n): dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
best_city, best_count = -1, n
for city in range(n):
count = sum(1 for j in range(n) if j != city and dist[city][j] <= distanceThreshold)
if count <= best_count:
best_count = count
best_city = city
return best_city
print(findTheCity(4,[[0,1,3],[1,2,1],[1,3,4],[2,3,1]],4)) # 3Ruta en un DAG ponderado
En un grafo acíclico dirigido (DAG), las rutas más cortas (o más largas) pueden encontrarse mediante ordenación topológica + relajación en O(V+E), más rápido que Dijkstra. Procese los nodos en orden topológico; al procesar el nodo u, relaje todas las aristas salientes. Para las rutas más largas (útiles en la planificación de proyectos o la ruta crítica), niegue los pesos o cambie min por max.
from collections import deque
def dag_shortest_path(V, edges, source):
graph = [[] for _ in range(V)]
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
# Topological sort (Kahn's)
queue = deque(i for i in range(V) if in_degree[i] == 0)
topo = []
while queue:
node = queue.popleft(); topo.append(node)
for nxt, _ in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
# Relax in topological order
dist = [float('inf')] * V
dist[source] = 0
for u in topo:
if dist[u] != float('inf'):
for v, w in graph[u]:
dist[v] = min(dist[v], dist[u] + w)
return distRuta más corta en una matriz con obstáculos
Una variante frecuente en entrevistas consiste en encontrar la ruta más corta en una cuadrícula 2D desde la esquina superior izquierda hasta la inferior derecha, donde algunas celdas pueden estar bloqueadas. Este es un problema de BFS no ponderado (cada paso cuesta 1). Use BFS con movimiento en cuatro direcciones y marque las celdas como visitadas cuando las introduzca en la cola (no cuando las extraiga) para evitar volver a visitarlas. Si los obstáculos se pueden atravesar y hacerlo tiene un coste, use Dijkstra sobre la cuadrícula 2D, tratándola como un grafo ponderado.
from collections import deque
def shortest_path_binary_matrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n-1][n-1] == 1:
return -1
queue = deque([(0, 0, 1)]) # (row, col, distance)
visited = {(0, 0)}
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
while queue:
r, c, d = queue.popleft()
if r == n-1 and c == n-1:
return d
for dr, dc in dirs:
nr, nc = r+dr, c+dc
if 0<=nr<n and 0<=nc<n and grid[nr][nc]==0 and (nr,nc) not in visited:
visited.add((nr,nc))
queue.append((nr, nc, d+1))
return -1
print(shortest_path_binary_matrix([[0,0,0],[1,1,0],[1,1,0]])) # 4BFS de múltiples fuentes
Cuando existen varios puntos de partida (por ejemplo, varias «puertas» en una cuadrícula o varios orígenes en un mapa), ejecute un BFS de múltiples fuentes: introduzca todas las fuentes en la cola con distancia 0 simultáneamente. Esto calcula la distancia más corta desde la fuente más cercana hasta cada celda en una sola pasada de BFS. Esta técnica evita ejecutar BFS por separado desde cada fuente y tiene un coste total de O(V+E).
Resumen de la selección de algoritmos
Árbol de decisión conciso: un solo origen, pesos no negativos → Dijkstra O((V+E) log V). Un solo origen, pesos negativos → Bellman-Ford O(VE). Todos los pares, V pequeño → Floyd-Warshall O(V³). DAG, cualquier peso → ordenación topológica + relajación O(V+E). No ponderado → BFS O(V+E). Rutas en cuadrículas → BFS (no ponderado) o Dijkstra con montículo (ponderado). Memorice esta tabla: responde a las preguntas de seguimiento en cualquier entrevista sobre rutas más cortas.
Búsqueda de rutas en preguntas de entrevista
Muchos problemas de entrevistas solicitan la ruta real, no solo el coste. Aclare siempre: ¿necesita la ruta o solo la distancia? Si necesita la ruta, asigne un diccionario prev desde el principio. Errores frecuentes: olvidar inicializar prev[source] = None como condición terminal y confundir el orden de reconstrucción (retroceder del destino al origen y después invertir la ruta). Practique la reconstrucción de rutas con ejemplos de 3 o 4 nodos antes de aplicarla a problemas más grandes.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: Network Delay Time se resuelve con max(dist.values()) después de ejecutar Dijkstra, la reconstrucción de rutas utiliza un arreglo prev que se actualiza cada vez que mejora dist[v] y el BFS bidireccional puede reducir a la mitad el espacio de búsqueda para rutas más cortas no ponderadas entre un único par. A continuación, abordará el ordenamiento de grafos con el algoritmo de Kahn para la ordenación topológica.
Preguntas frecuentes
¿La lección «Network Delay Time y reconstrucción de caminos» es gratis?
Sí — el texto completo de «Network Delay Time y reconstrucción de caminos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Network Delay Time y reconstrucción de caminos»?
Resuelva network-delay-time con Dijkstra, reconstruya el camino mínimo real mediante un mapa de predecesores y analice BFS bidireccional para grafos grandes. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Network Delay Time y reconstrucción de caminos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Algoritmo de Dijkstra con una cola de prioridad
- Bellman-Ford y ciclos negativos
- Floyd-Warshall: caminos mínimos entre todos los pares
- Network Delay Time y reconstrucción de caminos