LeetCode 743: Network Delay Time

Problem Restatement

We are given a directed weighted graph with n nodes labeled from 1 to n.

The input times contains directed edges:

[u, v, w]

This means a signal can travel from node u to node v in w time.

A signal starts from node k.

We need to return the minimum time needed for all nodes to receive the signal.

If some node cannot receive the signal, return -1.

The official statement gives times[i] = (ui, vi, wi) as directed travel times and asks for the minimum time for all n nodes to receive the signal. If impossible, return -1. The constraints include 1 <= k <= n <= 100, times.length <= 6000, and unique directed pairs.

Input and Output

Example function shape:

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    ...

Examples

Example 1

times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2

The signal starts at node 2.

It reaches:

The last node receives the signal at time 2.

So the answer is:

2

Example 2

times = [[1, 2, 1]]
n = 2
k = 1

The signal starts at node 1.

It reaches node 2 in time 1.

So the answer is:

1

Example 3

times = [[1, 2, 1]]
n = 2
k = 2

The signal starts at node 2.

There is no outgoing edge from node 2, so node 1 cannot receive the signal.

The answer is:

-1

First Thought: Try All Paths

One possible approach is to explore every path from k.

For each node, keep the smallest time found so far.

But a graph may have many possible paths. Trying paths naively can repeat a large amount of work.

We need a shortest path algorithm.

Because all edge weights are non-negative, Dijkstra’s algorithm fits this problem.

Key Insight

The time when a node receives the signal is the shortest path distance from k to that node.

The answer is not the sum of all shortest paths.

The signal spreads through the network. All edges can carry the signal outward as soon as their source receives it.

So after computing the shortest time to every node, the total delay is:

max(shortest_time_to_each_node)

because the last node to receive the signal determines the total time.

If any node has no shortest time, it is unreachable.

Algorithm

Build an adjacency list:

graph[u] = [(v, w), ...]

Then run Dijkstra’s algorithm from node k.

1. Create a min-heap containing (0, k).
2. Create a dictionary dist for finalized shortest times.
3. While the heap is not empty:
   • Pop the pair with the smallest time.
   • If the node was already finalized, skip it.
   • Store its shortest time.
   • Push all outgoing neighbors with updated time.
4. If fewer than n nodes were finalized, return -1.
5. Otherwise, return the maximum finalized distance.

Correctness

Dijkstra’s algorithm always processes the not-yet-finalized node with the smallest known arrival time.

Because all edge weights are non-negative, once a node is popped from the heap for the first time, no later path can reach that node faster. Therefore the first popped time for each node is its true shortest signal arrival time.

The algorithm stores each node’s finalized shortest time in dist. For each outgoing edge, it pushes the candidate arrival time for the neighbor. Thus every reachable path from k is represented by some heap candidate, and the shortest candidate for each node is eventually finalized.

If fewer than n nodes are finalized, at least one node is unreachable from k, so returning -1 is correct.

Otherwise, every node has a shortest signal arrival time. Since the signal reaches all nodes by the time the slowest reachable node receives it, the required network delay is the maximum value in dist.

Complexity

Let V = n and E = len(times).

This is often written as O(E log V) with a standard Dijkstra implementation.

Implementation

from collections import defaultdict
import heapq

class Solution:
    def networkDelayTime(
        self,
        times: list[list[int]],
        n: int,
        k: int,
    ) -> int:
        graph = defaultdict(list)

        for u, v, w in times:
            graph[u].append((v, w))

        heap = [(0, k)]
        dist = {}

        while heap:
            time, node = heapq.heappop(heap)

            if node in dist:
                continue

            dist[node] = time

            for neighbor, weight in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(
                        heap,
                        (time + weight, neighbor),
                    )

        if len(dist) != n:
            return -1

        return max(dist.values())

Code Explanation

We build the graph as an adjacency list:

graph = defaultdict(list)

for u, v, w in times:
    graph[u].append((v, w))

Each edge is directed, so we only add v to u’s list.

The heap starts at the source node with time 0:

heap = [(0, k)]

The dictionary dist stores finalized shortest times:

dist = {}

When we pop from the heap:

time, node = heapq.heappop(heap)

we skip the node if it already has a finalized distance:

if node in dist:
    continue

Otherwise, this is the shortest time to that node:

dist[node] = time

Then we push candidate times for all outgoing neighbors:

for neighbor, weight in graph[node]:
    if neighbor not in dist:
        heapq.heappush(
            heap,
            (time + weight, neighbor),
        )

At the end, all nodes must have been reached:

if len(dist) != n:
    return -1

If so, the answer is the time of the slowest node:

return max(dist.values())

Testing

def run_tests():
    s = Solution()

    assert s.networkDelayTime(
        [[2, 1, 1], [2, 3, 1], [3, 4, 1]],
        4,
        2,
    ) == 2

    assert s.networkDelayTime(
        [[1, 2, 1]],
        2,
        1,
    ) == 1

    assert s.networkDelayTime(
        [[1, 2, 1]],
        2,
        2,
    ) == -1

    assert s.networkDelayTime(
        [[1, 2, 5], [1, 3, 1], [3, 2, 1]],
        3,
        1,
    ) == 2

    assert s.networkDelayTime(
        [[1, 2, 0], [2, 3, 0]],
        3,
        1,
    ) == 0

    print("all tests passed")

run_tests()