Editorial: Network Delay Time

by admin · Oct. 18, 2026

1 Intuition

The answer is the largest shortest-path distance from k.

2 Approach

Run Dijkstra from k with a min-heap. If some node is unreachable return −1, otherwise return the maximum distance.

3 Complexity Analysis

Time O(E log V), Space O(V + E).

4 Solution Code

class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        import heapq
        graph = {}
        for u, v, w in times:
            graph.setdefault(u, []).append((v, w))
        dist = {}
        heap = [(0, k)]
        while heap:
            d, u = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = d
            for v, w in graph.get(u, []):
                if v not in dist:
                    heapq.heappush(heap, (d + w, v))
        return max(dist.values()) if len(dist) == n else -1

5 Code Walkthrough

The reference solution below implements the approach step by step.