⚡Flashcard Drill➔
NeetCode #628LC-743MediumAdvanced GraphsNC 150NC 250
← Back to All Problems

#628 · #743 · Network Delay Time(网络延迟时间)

📌 Problem Statement & Constraints

You are given times where times[i] = [u, v, w] is a directed edge taking w time, and n nodes labelled 1..n. Starting from node k, return the time for all nodes to receive the signal, or -1 if impossible. Constraints: 1 <= k <= n <= 100, 1 <= times.length <= 6000, 0 <= w <= 100.

💡 Core Algorithmic Approaches

  1. This is the single-source shortest path problem, so Dijkstra applies (all weights are non-negative).
  2. Use a min-heap of (distance, node); settle each node once.
  3. The answer is the maximum settled distance, provided all n nodes are reached.
  4. The lazy-deletion pattern (skip nodes already settled) keeps the heap simple.

💻 Benchmark Python3 Implementation

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        import heapq
        from collections import defaultdict
        g = defaultdict(list)
        for u, v, w in times:
            g[u].append((v, w))
        dist = {}
        h = [(0, k)]
        while h:
            d, node = heapq.heappop(h)
            if node in dist:
                continue                   # already settled with a smaller distance
            dist[node] = d
            for nxt, w in g[node]:
                if nxt not in dist:
                    heapq.heappush(h, (d + w, nxt))
        return max(dist.values()) if len(dist) == n else -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(E log V): each edge is relaxed once.
💾 Space Complexity
O(V + E) for the graph and the distance map.

⚠️ Interview Pitfalls & Follow-ups

  • Using BFS: the weights differ, so a plain queue does not give shortest paths.
  • Marking settled when pushing: a shorter path could arrive later and be ignored.
  • Forgetting the unreachable check: some nodes may never receive the signal.
  • Using Bellman-Ford: correct but slower; Dijkstra is the right tool for non-negative weights.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems