Skip to content

Network Delay Time

Problem

Given a network of n nodes (1-indexed) and directed weighted edges times[i] = (u, v, w), send a signal from node k. Return the minimum time for all nodes to receive the signal, or -1 if not all nodes are reachable.

Approach

Run Dijkstra from source k. The answer is the maximum shortest distance among all nodes. If any node is unreachable, return -1.

When to Use

"Can a signal/message reach all nodes, and how long?" — broadcast latency, all-nodes reachability. Run Dijkstra, answer is max(dist). Aviation: minimum propagation delay across a network of stations.

Complexity
Time O((V + E) log V)
Space O(V + E)

Implementation

network_delay_time

Time for a signal to reach all nodes (Dijkstra variant).

Problem

Given a network of n nodes (1-indexed) and directed weighted edges times[i] = (u, v, w), send a signal from node k. Return the minimum time for all nodes to receive the signal, or -1 if not all nodes are reachable.

Approach

Run Dijkstra from source k. The answer is the maximum shortest distance among all nodes. If any node is unreachable, return -1.

When to use

"Can a signal/message reach all nodes, and how long?" — broadcast latency, all-nodes reachability. Run Dijkstra, answer is max(dist). Aviation: minimum propagation delay across a network of stations.

Complexity

Time: O((V + E) log V) Space: O(V + E)

network_delay_time 

network_delay_time(
    times: list[tuple[int, int, int]], n: int, k: int
) -> int

Return minimum time for signal from k to reach all n nodes.

Nodes are 1-indexed. Returns -1 if any node is unreachable.

network_delay_time([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2) 2

Source code in src/algo/graphs/network_delay_time.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def network_delay_time(
    times: list[tuple[int, int, int]],
    n: int,
    k: int,
) -> int:
    """Return minimum time for signal from *k* to reach all *n* nodes.

    Nodes are 1-indexed.  Returns -1 if any node is unreachable.

    >>> network_delay_time([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2)
    2
    """
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))

    dist: list[float] = [INF] * (n + 1)
    dist[k] = 0
    heap: list[tuple[float, int]] = [(0, k)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    max_dist = max(dist[1:])
    return int(max_dist) if max_dist < INF else -1
tests/graphs/test_network_delay_time.py
"""Tests for network delay time."""

from algo.graphs.network_delay_time import network_delay_time


class TestNetworkDelayTime:
    def test_basic(self) -> None:
        times = [(2, 1, 1), (2, 3, 1), (3, 4, 1)]
        assert network_delay_time(times, 4, 2) == 2

    def test_unreachable(self) -> None:
        times = [(1, 2, 1)]
        assert network_delay_time(times, 3, 1) == -1

    def test_single_node(self) -> None:
        assert network_delay_time([], 1, 1) == 0

    def test_two_paths(self) -> None:
        times = [(1, 2, 10), (1, 3, 1), (3, 2, 2)]
        assert network_delay_time(times, 3, 1) == 3

    def test_all_directly_connected(self) -> None:
        times = [(1, 2, 5), (1, 3, 3), (1, 4, 7)]
        assert network_delay_time(times, 4, 1) == 7

Implement it yourself

Run: just challenge graphs network_delay_time

Then implement the functions to make all tests pass. Use just study graphs for watch mode.

Reveal Solution

network_delay_time

Time for a signal to reach all nodes (Dijkstra variant).

Problem

Given a network of n nodes (1-indexed) and directed weighted edges times[i] = (u, v, w), send a signal from node k. Return the minimum time for all nodes to receive the signal, or -1 if not all nodes are reachable.

Approach

Run Dijkstra from source k. The answer is the maximum shortest distance among all nodes. If any node is unreachable, return -1.

When to use

"Can a signal/message reach all nodes, and how long?" — broadcast latency, all-nodes reachability. Run Dijkstra, answer is max(dist). Aviation: minimum propagation delay across a network of stations.

Complexity

Time: O((V + E) log V) Space: O(V + E)

network_delay_time 

network_delay_time(
    times: list[tuple[int, int, int]], n: int, k: int
) -> int

Return minimum time for signal from k to reach all n nodes.

Nodes are 1-indexed. Returns -1 if any node is unreachable.

network_delay_time([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2) 2

Source code in src/algo/graphs/network_delay_time.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def network_delay_time(
    times: list[tuple[int, int, int]],
    n: int,
    k: int,
) -> int:
    """Return minimum time for signal from *k* to reach all *n* nodes.

    Nodes are 1-indexed.  Returns -1 if any node is unreachable.

    >>> network_delay_time([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2)
    2
    """
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))

    dist: list[float] = [INF] * (n + 1)
    dist[k] = 0
    heap: list[tuple[float, int]] = [(0, k)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    max_dist = max(dist[1:])
    return int(max_dist) if max_dist < INF else -1