The machine must compute how long it takes a signal to reach every node in a weighted directed graph starting from node k. If any node is unreachable, the answer is -1. Positive edge weights make this exactly the single-source shortest-path problem.
The key insight is that the answer is the maximum of all shortest-path distances: the signal spreads in parallel, so the total delay is when the slowest node receives it. Dijkstra's algorithm with a min-heap computes those distances by always expanding the closest unsettled node first.
The approach has three steps. First, build an adjacency list from the times array and initialize distances to infinity, with dist[k] = 0. Second, pop the smallest tentative distance from the heap, skip stale entries, and relax each outgoing edge, pushing any improvement back onto the heap. Third, when the heap empties, the largest finite distance is the answer, or -1 if a node is still at infinity. With E edges and V nodes, time is O(E log V) and space is O(V + E).
The trickiest edge case is the disconnected graph: a node that never receives the signal keeps distance infinity, and the machine must return -1 rather than a maximum over reachable nodes only. Parallel edges with different weights are handled by the relaxation check.
import heapq
def networkDelayTime(times, n, k):
adj = [[] for _ in range(n + 1)]
for u, v, w in times:
adj[u].append((v, w))
dist = [float('inf')] * (n + 1)
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
max_delay = max(dist[1:])
return max_delay if max_delay < float('inf') else -1