Network Delay Time and Path Reconstruction
Solve network-delay-time with Dijkstra, reconstruct the actual shortest path using a predecessor map, and discuss bidirectional BFS for large graphs.
Network Delay Time Problem
Network Delay Time (LeetCode 743): given a network of n nodes and directed weighted edges representing signal travel times, find the minimum time for a signal sent from node k to reach all nodes. If some node is unreachable, return -1. This is a direct application of Dijkstra: the answer is the maximum shortest-path distance from k across all nodes.
Solution: Dijkstra + Max of Distances
Run Dijkstra from source k to find dist[v] for all nodes v. The answer is max(dist.values()). If any dist[v] is still inf, that node is unreachable — return -1. The signal travels all paths simultaneously, so the bottleneck is the node that takes the longest to reach.
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)) # 2All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction