DSAPrep
MediumAdvanced Graphs

Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: The signal reaches node 1 and node 3 at time 1, then reaches node 4 (via node 3) at time 2. All nodes have received it by time 2.

Example 2

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

Example 3

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: Node 2 has no outgoing edge, so node 1 can never be reached from it.

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 the pairs (u_i, v_i) are unique.
View original on LeetCode ↗

This is single-source shortest path on a directed, positively-weighted graph — the textbook setup for Dijkstra’s algorithm. The signal “reaches all nodes” at the time equal to the largest of the individual shortest distances from k, since every node needs its own shortest path to receive the signal, and the whole network is “done” only once the slowest node has heard it.

Bellman-Ford (Relax Every Edge n-1 Times)

Time O(n · E)Space O(n)

Without assuming anything about edge order, the safest way to compute shortest paths is to relax every edge repeatedly. After i rounds, every shortest path using at most i edges is guaranteed correct. Since a shortest simple path in a graph with n nodes uses at most n - 1 edges, n - 1 rounds suffice.

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        INF = float('inf')
        dist = [INF] * (n + 1)
        dist[k] = 0


        for _ in range(n - 1):
            for u, v, w in times:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w


        farthest = max(dist[1:])
        return -1 if farthest == INF else farthest

Each of the n - 1 rounds scans all E edges, so this costs O(n · E) time — noticeably worse than Dijkstra when the graph is dense, but it works fine here (it does not need a priority queue and tolerates negative weights, though this problem doesn’t have any). Space is O(n) for the distance array.

Dijkstra's Algorithm with a Min-Heap

OptimalTime O(E log V)Space O(V + E)

Since all weights are non-negative, Dijkstra’s algorithm is strictly better: it greedily finalizes the closest unvisited node at each step, using a min-heap to always pop the currently-nearest frontier node. Once a node is popped with its finalized distance, it never needs to be revisited — no negative edge can ever produce a shorter path later.

import heapq
from collections import defaultdict


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))


        dist = {}
        pq = [(0, k)]  # (distance, node)


        while pq:
            d, node = heapq.heappop(pq)
            if node in dist:          # already finalized with a smaller distance
                continue
            dist[node] = d
            for nei, w in graph[node]:
                if nei not in dist:
                    heapq.heappush(pq, (d + w, nei))


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

Worked example — times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2. Adjacency: 2 → 1 (1), 2 → 3 (1), 3 → 4 (1).

Watch the frontier finalize in heap order: each pop turns a node emerald with a check, its freshly reached neighbors light up indigo with new tentative distances, and every candidate waiting its turn sits in the amber heap below — where the flagged top entry shows exactly which node pops next.

111
1
2
3
4
∞
0
∞
∞

Min-heap · (distance, node)

(0, 2)

▲ top of heap pops first

1 / 8
tentative distanceheap candidatesettled (final)

Start: nodes 1, 3 and 4 are unreached (infinite distance). The source k = 2 gets tentative distance 0 and becomes the only heap entry, (0, 2). The heap always offers the smallest remaining (distance, node), so node 2 is the confirmed next pop.

The pops came in order (0,2) → (1,1) → (1,3) → (2,4) and the finalized distances are {2: 0, 1: 1, 3: 1, 4: 2}. All 4 nodes are finalized, so the answer is max(dist.values()) = 2 — the moment the slowest node (node 4) hears the signal.

Why it’s correct: the heap always pops the unfinalized node with the smallest tentative distance. Because every edge weight is non-negative, that popped distance can never be improved by a path through a node that hasn’t been finalized yet (any such path would already be at least as long). This is the standard Dijkstra correctness argument.

Complexity: every edge can trigger at most one heap push, so there are O(E) heap operations, each O(log E) = O(log V) (since E ≤ V²) — O(E log V) time. The adjacency list and heap both hold O(V + E) entries — O(V + E) space.