Network Delay Time

Medium

💭 Introduction

You’re given a network of n nodes labeled from 1 to n. You’re also given a list of travel times as directed edges times[i] = (ui, vi, wi), where:

ui is the source node
vi is the target node
wi is the time it takes for a signal to travel from source to target

Your task: Send a signal from node k and find the minimum time for all nodes to receive the signal. If it’s impossible, return -1.

This is a classic application of Dijkstra’s Algorithm — finding the shortest path from a single source to all other nodes in a weighted graph.

🧩 Problem Statement

LeetCode #743 — Network Delay Time

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.

🔍 Example 1:

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

Explanation:

Network:
    1 ← 1 ← 2
            ↓ 1
            3
            ↓ 1
            4

Signal sent from node 2:
- Node 2: time = 0 (source)
- Node 1: time = 1 (2 → 1)
- Node 3: time = 1 (2 → 3)
- Node 4: time = 2 (2 → 3 → 4)

Maximum time = 2

🔍 Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Explanation:

Network: 1 → 2 (weight 1)

Signal sent from node 1:
- Node 1: time = 0
- Node 2: time = 1

Maximum time = 1

🔍 Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Explanation:

Network: 1 → 2 (weight 1)

Signal sent from node 2:
- Node 2: time = 0
- Node 1: unreachable!

Return -1 (not all nodes can receive signal)

🧠 Step 1: Understanding the Problem

Let’s break down what we’re really asking:

Key Observations:

Directed weighted graph: Edges have direction and weights (travel times)
Single source: Signal starts from node k
All nodes must receive: We need to reach every node
Minimum time: We want the shortest path to each node
Answer is maximum: The time when the last node receives the signal

Why Dijkstra’s Algorithm?

We need shortest paths from a single source → Perfect for Dijkstra
All edge weights are positive (travel times) → Dijkstra works
We need to reach all nodes → Run Dijkstra completely, then find max distance

Transform the problem:

"Minimum time for all nodes to receive signal"
        ↓
"Maximum of all shortest paths from source"

🤔 Step 2: The Brute Force Approach (BFS)

We could try BFS, but it doesn’t handle weighted graphs optimally:

from collections import deque, defaultdict

def networkDelayTime(times, n, k):
    # Build graph
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    # BFS won't work correctly for weighted graphs!
    # This is just to show why we need Dijkstra
    queue = deque([(k, 0)])  # (node, time)
    visited = {k: 0}
    
    while queue:
        node, time = queue.popleft()
        
        for neighbor, weight in graph[node]:
            new_time = time + weight
            if neighbor not in visited or new_time < visited[neighbor]:
                visited[neighbor] = new_time
                queue.append((neighbor, new_time))
    
    if len(visited) != n:
        return -1
    
    return max(visited.values())

Problem: BFS doesn’t guarantee we process nodes in order of shortest distance!

🚀 Step 3: Dijkstra’s Algorithm Solution

The optimal solution uses Dijkstra’s algorithm with a priority queue:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, 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
        # dist[node] = shortest time to reach node from k
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0
        
        # Priority queue: (time, node)
        pq = [(0, k)]
        
        while pq:
            current_time, node = heapq.heappop(pq)
            
            # Skip if we've already found a better path
            if current_time > dist[node]:
                continue
            
            # Explore neighbors
            for neighbor, travel_time in graph[node]:
                new_time = current_time + travel_time
                
                # If we found a shorter path, update it
                if new_time < dist[neighbor]:
                    dist[neighbor] = new_time
                    heapq.heappush(pq, (new_time, neighbor))
        
        # Find maximum time (when last node receives signal)
        max_time = max(dist.values())
        
        # If any node is unreachable, return -1
        return max_time if max_time != float('inf') else -1

⏱️ Time Complexity: $O((V + E) \log V)$ where V = n nodes, E = len(times) edges

📦 Space Complexity: $O(V + E)$ for graph and priority queue

⚙️ Step 4: Step-by-Step Trace

Let’s trace through Example 1: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Graph representation:

→ 1 (weight 1)
→ 3 (weight 1)
→ 4 (weight 1)

Execution trace:

Step	PQ (time, node)	Current	Visited	dist[1]	dist[3]	dist[4]	Action
0	[(0, 2)]	-	{}	∞	∞	∞	Initialize
1	[(1, 1), (1, 3)]	2	{2}	1	1	∞	Process 2, update 1 and 3
2	[(1, 3)]	1	{2, 1}	1	1	∞	Process 1, no neighbors
3	[(2, 4)]	3	{2, 1, 3}	1	1	2	Process 3, update 4
4	[]	4	{2, 1, 3, 4}	1	1	2	Process 4, no neighbors

Final distances: [1, 0, 1, 2]

Maximum time: 2 ✓

🎯 Step 5: Alternative Implementation (Using Set)

Using a visited set instead of checking distances:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # Build graph
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # Track shortest distances
        dist = {}
        pq = [(0, k)]
        
        while pq:
            time, node = heapq.heappop(pq)
            
            # Skip if already visited
            if node in dist:
                continue
            
            # Record shortest time to this node
            dist[node] = time
            
            # Explore neighbors
            for neighbor, travel_time in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(pq, (time + travel_time, neighbor))
        
        # Check if all nodes were reached
        if len(dist) != n:
            return -1
        
        return max(dist.values())

This version is slightly cleaner and avoids the distance comparison check.

🧮 Step 6: Optimized with Early Termination

If we only care about reachability, we can terminate early:

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        dist = {}
        pq = [(0, k)]
        
        while pq and len(dist) < n:  # Early termination
            time, node = heapq.heappop(pq)
            
            if node in dist:
                continue
            
            dist[node] = time
            
            for neighbor, travel_time in graph[node]:
                if neighbor not in dist:
                    heapq.heappush(pq, (time + travel_time, neighbor))
        
        return max(dist.values()) if len(dist) == n else -1

🎯 Key Insights

Maximum of minimums: Answer is the maximum shortest path distance
Directed graph: Edge direction matters — can’t go backwards
Reachability check: If any node unreachable, return -1
Priority queue essential: Ensures we process nodes in order of shortest distance
Dijkstra’s perfect fit: Single source, non-negative weights, need all shortest paths

📊 Complexity Summary

Approach	Time	Space	Notes
BFS (incorrect)	$O(V + E)$	$O(V + E)$	Doesn’t work for weighted graphs
Dijkstra (heap)	$O((V + E) \log V)$	$O(V + E)$	Optimal solution
Dijkstra (array)	$O(V^2)$	$O(V + E)$	Better for dense graphs

🌟 Edge Cases to Consider

Single node: n = 1, k = 1 → Return 0
Disconnected graph: Some nodes unreachable → Return -1
Source not in graph: k has no outgoing edges → Check if n = 1
Self-loops: Can be ignored (don’t improve shortest path)
Multiple edges: Keep all (Dijkstra handles automatically)
All nodes reachable: Return maximum distance

💡 Common Mistakes

Using BFS instead of Dijkstra: BFS doesn’t handle weights correctly
Forgetting to check reachability: Must verify all n nodes are reached
Wrong answer calculation: Need maximum, not sum of distances
1-indexed nodes: Nodes are labeled 1 to n, not 0 to n-1
Not handling disconnected components: Some nodes might be unreachable

🧪 Test Cases

# Test Case 1: Basic example
times = [[2,1,1],[2,3,1],[3,4,1]]
n = 4
k = 2
# Expected: 2

# Test Case 2: Single edge
times = [[1,2,1]]
n = 2
k = 1
# Expected: 1

# Test Case 3: Unreachable node
times = [[1,2,1]]
n = 2
k = 2
# Expected: -1

# Test Case 4: Multiple paths
times = [[1,2,1],[2,3,2],[1,3,4]]
n = 3
k = 1
# Expected: 3 (1→2→3 is shorter than 1→3)

# Test Case 5: Single node
times = []
n = 1
k = 1
# Expected: 0

🔍 Variations of This Problem

Minimum Cost to Reach Destination - Similar but with cost constraints
Cheapest Flights Within K Stops - With hop limit
Path with Maximum Probability - Maximize instead of minimize
Shortest Path with Alternating Colors - Additional constraints

Dijkstra’s Algorithm - The core algorithm
Cheapest Flights Within K Stops (LC 787) - With constraints
Path with Maximum Probability (LC 1514) - Modified Dijkstra
Minimum Cost to Reach City (LC 1334) - Similar pattern

🏆 Why This Problem Matters

Real-world application: Models actual network delay scenarios
Dijkstra practice: Perfect problem to learn the algorithm
Interview favorite: Common in technical interviews
Graph fundamentals: Tests understanding of weighted directed graphs
Practical relevance: Used in networking, routing, telecommunications

🎓 Key Takeaways

Recognize the pattern: Single source shortest path → Dijkstra
Answer is maximum: Last node to receive signal determines total time
Check reachability: Not all nodes might be reachable
Priority queue is key: Ensures optimal processing order
1-indexed nodes: Be careful with node numbering

📝 Interview Tips

Clarify constraints: Confirm nodes are 1-indexed, edges are directed
Explain Dijkstra: Show you understand why it’s the right choice
Handle edge cases: Discuss unreachable nodes, single node
Optimize if asked: Mention early termination possibility
Test thoroughly: Walk through a small example
Discuss complexity: Explain time and space complexity clearly

🔧 Python Tips

# Using defaultdict for cleaner graph building
from collections import defaultdict
graph = defaultdict(list)

# Dictionary comprehension for initialization
dist = {i: float('inf') for i in range(1, n + 1)}

# Heap operations
heapq.heappush(pq, (time, node))  # Add to heap
time, node = heapq.heappop(pq)     # Remove minimum

# Check if all nodes reached
if len(dist) == n:  # All nodes have finite distance
    return max(dist.values())

🎯 Problem-Solving Pattern

This problem follows the Single-Source Shortest Path pattern:

Identify: Need shortest paths from one source to all nodes
Check weights: All non-negative → Use Dijkstra
Build graph: Create adjacency list from edge list
Run Dijkstra: Use priority queue for efficiency
Extract answer: Maximum distance (or check reachability)

This pattern applies to many similar problems in graph theory!

Network Delay Time

💭 Introduction

🔍 Example 1:

🔍 Example 2:

🔍 Example 3:

🧠 Step 1: Understanding the Problem

🤔 Step 2: The Brute Force Approach (BFS)

🚀 Step 3: Dijkstra’s Algorithm Solution

⚙️ Step 4: Step-by-Step Trace

🎯 Step 5: Alternative Implementation (Using Set)

🧮 Step 6: Optimized with Early Termination

🎯 Key Insights

📊 Complexity Summary

🌟 Edge Cases to Consider

💡 Common Mistakes

🧪 Test Cases

🔍 Variations of This Problem

💡 Related Problems

🏆 Why This Problem Matters

🎓 Key Takeaways

📝 Interview Tips

🔧 Python Tips

🎯 Problem-Solving Pattern