743. Network Delay Time

Metric	Complexity	Explanation
Time	$O((V + E) \log V)$	Each edge relaxation may push to heap; heap ops are $O(\log V)$
Space	$O(V + E)$	Adjacency list $O(E)$ , distance array $O(V)$ , heap up to $O(E)$

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        G = defaultdict(list)
        for u, v, w in times:
            G[u].append([v, w])
        
        W = [inf] * (n + 1)
        W[k] = 0
        heap = [(0, k)]

        while heap:
            w, node = heappop(heap)

            for nei, nei_w in G[node]:
                nw = w + nei_w
                if nw < W[nei]:
                    W[nei] = nw
                    heappush(heap, [nw, nei])

        result = max(W[1:])
        return -1 if result == inf else result

Metric	Complexity	Explanation
Time	$O(V \cdot E)$	$n-1$ iterations, each relaxing all $E$ edges
Space	$O(V)$	Distance array only

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        W = [inf] * (n + 1)
        W[k] = 0

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

        result = max(W[1:])
        return result if result != inf else -1