MediumDepth-First SearchBreadth-First SearchGraphHeap (Priority Queue)Shortest Path

Network Delay Time

1 approach, code in every language

You are given a network of `n` nodes labeled from `1` to `n`. Travel times are described by a list `times`, where each entry `times[i] = [u, v, w]` means a signal takes `w` units of time to travel along a directed edge from node `u` to node `v`.

A signal is emitted from a single source node `k`. Return the amount of time it takes for the signal to reach every node in the network. If it is impossible for at least one node to receive the signal, return `-1`.

Because a node lights up as soon as the signal first arrives, the time for the whole network to be covered is the latest of all the individual arrival times.

Example 1

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

Output: 2

From node 2 the signal reaches node 1 at time 1 and node 3 at time 1, then continues from 3 to node 4 at time 2. The slowest arrival is 2.

Example 2

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

Output: -1

The only edge points from 1 to 2, so starting at node 2 there is no way to reach node 1. One node stays unreachable, so the answer is -1.

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u_i, v_i <= n
u_i != v_i
0 <= w_i <= 100
All pairs (u_i, v_i) are unique (no multiple edges).

Dijkstra with a Min-Heap

Run Dijkstra from the source with a min-heap keyed on distance; the answer is the largest settled distance, or -1 if a node is unreachable.

Loading animation…

Intuition

The signal spreads outward from k along weighted edges, and the time for any node to light up equals the shortest weighted path from k to it. That is precisely a single-source shortest-path problem on a graph with non-negative weights, which Dijkstra solves efficiently. A min-heap always returns the closest node that has not been finalized yet, so each node's first pop gives its true shortest arrival time. The moment the whole network is covered is therefore the slowest of those shortest times. If some node has no path from k it stays at infinity, and the answer is -1.

Algorithm walkthrough

1Build a directed adjacency list mapping each source node to its list of (neighbor, weight) pairs.
2Initialize a dist array to infinity, set dist[k] = 0, and push (0, k) onto a min-heap ordered by distance.
3Repeatedly pop the smallest (d, node); if d is greater than the recorded dist[node] it is a stale entry, so skip it.
4Relax each outgoing edge: if d + weight beats the neighbor's known distance, update it and push the new pair.
5Because the heap always settles the closest unsettled node first, every node is finalized exactly once.
6After the heap drains, return the largest finalized distance; if any node is still infinity it was never reached, so return -1.

Implementation

import heapq
from typing import List


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = [[] for _ in range(n + 1)]
        for u, v, w in times:
            graph[u].append((v, w))

        dist = [float("inf")] * (n + 1)
        dist[k] = 0
        heap = [(0, k)]

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

        ans = max(dist[1:])
        return ans if ans < float("inf") else -1

Time

O(E log N)

Space

O(N + E)

E is the number of edges and N the number of nodes; skipping stale heap entries keeps each node's relaxation to its first, minimal pop.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Relay Broadcast Time is our own problem on the technique behind Network Delay Time: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free