Problem Breakdown
We are given a directed graph where nodes represent network stations and edges represent signal transmission times. The goal is to calculate the time required for all n nodes to receive a signal starting from node k. This effectively requires finding the longest of the shortest paths (the maximum distance) among all reachable nodes in the single-source shortest path problem. If any node cannot be reached, the system fails (-1).
- Inputs:
times: List of directed edges[u, v, w].n: Number of nodes (labeled 1 to n).k: Source node index.
- Output: Integer representing for all , or
-1if unreachable.
Intuition
This problem is a classic application of the Single-Source Shortest Path algorithm on a weighted graph with non-negative edge weights ().
- Why not BFS/DFS? Standard Breadth-First Search (BFS) only works for unweighted graphs or finding shortest paths in terms of hop count, ignoring the
witravel times. Depth-First Search (DFS) does not guarantee visiting nodes by increasing distance order and can get stuck exploring long paths before shorter ones are found without a priority queue. - Why Dijkstra? Since edge weights are non-negative, we can greedily expand from the source node to always process the closest unvisited neighbor first using a Min-Heap (Priority Queue). This ensures that once a node is popped from the heap, its shortest distance from
khas been finalized. - Handling Disconnection: We must track distances for all nodes . If any node retains an initial value of infinity after processing, it means no path exists from
k, necessitating a return of-1.
Approach
- Graph Representation: Construct an adjacency list where each key is a source node and the value is a list of tuples
(target_node, weight). This allows efficient neighbor iteration during traversal. - Initialization:
- Create a distance array
distsof sizen + 1, initialized to infinity (float('inf')). The extra index accounts for the problem’s 1-based indexing (nodes 1 through n). - Set
dists[k] = 0.
- Create a distance array
- Priority Queue: Initialize a min-heap with
(distance, node)starting from(0, k). - Dijkstra Loop:
- While the heap is not empty:
- Pop the element with the smallest current distance
(d, u). - Check for stale entries (if
d > dists[u], skip). This handles cases where a node was updated multiple times before being popped. - For each neighbor
vofu: calculate potential new distancenew_dist = d + w. - If
new_dist < dists[v], updatedists[v]and push(new_dist, v)to the heap.
- Pop the element with the smallest current distance
- While the heap is not empty:
- Result Extraction: Iterate through indices to . If any node has a distance of infinity, return
-1. Otherwise, compute the maximum value in the valid distances array.
Complexity Analysis
- Time: or more precisely . We iterate over each edge once (), and heap operations take logarithmic time relative to the number of elements currently in the priority queue (bounded by edges). Given constraints , this is highly efficient.
- Space: required for the adjacency list, distance array, and heap storage.
Solution
import heapq
from collections import defaultdict
from typing import List
def networkDelayTime(times: List[List[int]], n: int, k: int) -> int:
# Build adjacency list for O(1) neighbor lookup
adj = defaultdict(list)
for u, v, w in times:
adj[u].append((v, w))
# Initialize distances to infinity; source starts at 0.
# Size is n + 1 because nodes are labeled 1 through n.
dists = [float('inf')] * (n + 1)
dists[k] = 0
# Min-heap stores tuples of (current_distance, node_index)
pq = [(0, k)]
while pq:
d, u = heapq.heappop(pq)
# If popped distance is greater than recorded shortest path, skip stale entry
if d > dists[u]:
continue
for v, w in adj[u]:
new_dist = d + w
if new_dist < dists[v]:
dists[v] = new_dist
heapq.heappush(pq, (new_dist, v))
# Check reachability and find max time among all nodes 1 to n
max_time = 0
for i in range(1, n + 1):
if dists[i] == float('inf'):
return -1
max_time = max(max_time, dists[i])
return max_time
Edge Cases Handled
- Unreachable Nodes: The code explicitly checks
dists[i]against infinity. If any node is unreachable from , the function returns-1. This handles disconnected subgraphs correctly. - Single Node Network (): When and ,
dists[1]remains 0 (no edges exist). The loop checks index 1, finds distance is not infinity, setsmax_time = max(0, 0), returning 0. This is correct as no travel time is needed for the single node to receive its own signal. - Zero Weights: Dijkstra handles correctly because non-negative weights are required; equal distances do not break correctness or termination order in a min-heap implementation.
- Import Dependencies: The solution includes necessary imports (
collections,typing) to ensure it runs standalone without relying on implicit environment assumptions, preventing NameErrors fordefaultdictorList.