LeetEye LeetEye
Hard Advanced Graphs ~5 min

Network Delay Time

advanced-graphs network-delay-time

Problem

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] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi 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 the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Examples

Example 1
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Key Insight

Dijkstra's algorithm: find shortest path from source to all nodes.

Dijkstra from source k to find shortest paths to all nodes. Answer = max shortest path. If any node unreachable, return -1.

How to Approach This Problem

Pattern Recognition: When you see keywords like network delay time advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 Dijkstra's is used because:
Answer: All of above
Dijkstra's finds shortest paths from one source to all nodes with non-negative weights.
2 We maintain for each node:
Answer: Both
Signal reaches all when the farthest node receives it.

Solution

import heapq
from collections import defaultdict

def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
    # Build adjacency list
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # Dijkstra's algorithm
    min_heap = [(0, k)]  # (time, node)
    dist = {}
    
    while min_heap:
        time, node = heapq.heappop(min_heap)
        
        if node in dist:
            continue
        
        dist[node] = time
        
        for neighbor, weight in graph[node]:
            if neighbor not in dist:
                heapq.heappush(min_heap, (time + weight, neighbor))
    
    # Check if all nodes reached
    if len(dist) == n:
        return max(dist.values())
    return -1

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye