Network Delay Time

Find when a signal from one node reaches every node in a weighted directed graph.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Network Delay Time: Finalize shortest signal times by always popping the cheapest pending path.

Input and goalFind when a signal from one node reaches every node in a weighted directed graph.

Initialize the source pathFor start=1, the min-heap contains only (distance 0, node 1); no node has a finalized distance yet.

visitedfrontier(0,1)

inputn=4, start=1

Recognize it

The input is a directed graph with nonnegative edge costs, and the task asks when a source reaches every node, so shortest paths from one source determine the answer.

Keep true

Whenever an unfinalized node is popped with the globally smallest pending cost, that cost is its shortest distance; duplicate heap entries for finalized nodes are safely ignored.

Reuse it

Reuse Dijkstra for nonnegative weighted routing: enqueue improved path candidates, trust only the first pop of each node, and derive the requested aggregate from finalized shortest distances.

Pattern: Dijkstra.

Simple idea: Always process the path with the lowest total cost next. Add each outgoing edge cost and put the new path in the heap.

import heapq
from collections import defaultdict

def network_delay_time(times: list[list[int]], node_count: int, start: int) -> int:
   graph: dict[int, list[tuple[int, int]]] = defaultdict(list)
   for source, target, cost in times:
      graph[source].append((target, cost))

   distances: dict[int, int] = {}
   heap = [(0, start)]

   while heap:
      distance, node = heapq.heappop(heap)
      if node in distances:
         continue

      distances[node] = distance
      for neighbor, cost in graph[node]:
         if neighbor not in distances:
            heapq.heappush(heap, (distance + cost, neighbor))

   return max(distances.values()) if len(distances) == node_count else -1

Cost: $O((V+E)\log V)$ time and $O(V+E)$ space.