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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Problem

Approach: Dijkstra’s Algorithm

The key insight is this is a shortest path problem. We need to find the shortest path from source k to all nodes, then return the maximum distance.

Implementation

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
        min_heap = [(0, k)]  # (time, node)
        distances = {}

        while min_heap:
            time, node = heapq.heappop(min_heap)

            if node in distances:
                continue

            distances[node] = time

            # Explore neighbors
            for neighbor, weight in graph[node]:
                if neighbor not in distances:
                    heapq.heappush(min_heap, (time + weight, neighbor))

        # Check if all nodes are reachable
        if len(distances) != n:
            return -1

        return max(distances.values())

Alternative Implementation (with distance array)

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))

        # Initialize distances
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0

        min_heap = [(0, k)]

        while min_heap:
            time, node = heapq.heappop(min_heap)

            if time > dist[node]:
                continue

            for neighbor, weight in graph[node]:
                new_time = time + weight
                if new_time < dist[neighbor]:
                    dist[neighbor] = new_time
                    heapq.heappush(min_heap, (new_time, neighbor))

        max_time = max(dist.values())
        return max_time if max_time != float('inf') else -1

Complexity Analysis

Time Complexity: O(E log N), where E is number of edges and N is number of nodes. Each edge is processed once and heap operations are O(log N).
Space Complexity: O(N + E) for the graph and distances.

Key Insights

Shortest Path: This is a single-source shortest path problem, perfect for Dijkstra’s algorithm.
Signal Propagation: The signal spreads from source k simultaneously along all edges, so we need the shortest paths to all nodes.
Maximum Distance: The time for all nodes to receive the signal is the maximum of all shortest paths (the farthest node).
Dijkstra with Min-Heap: We use a min-heap to always process the node with minimum current distance.
Visited Check: Once a node is processed (popped from heap), we’ve found its shortest path and don’t process it again.
Unreachable Nodes: If any node is unreachable from k, return -1.