Network Delay Time

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

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