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
Explanation: The signal starts at node 2. At time 0, node 2 receives the signal.
At time 1, nodes 1 and 3 receive the signal.
At time 2, node 4 receives the signal.
So the minimum time for all nodes to receive the signal is 2.

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: The signal starts at node 1. At time 1, node 2 receives the signal.
So the minimum time for all nodes to receive the signal is 1.

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: Node 2 cannot send a signal to node 1, so it's impossible for all nodes to receive the signal.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • There will not be any multiple edges (i.e., no duplicate edges).

Thinking Process

  1. Dijkstra’s Algorithm: Optimal for single-source shortest paths with non-negative weights
    • Adjacency matrix: Better for dense graphs (O(n²) time)
    • Adjacency list + min-heap: Better for sparse graphs (O((n+m)log n) time) - This is already optimal!
  • Model entities as nodes and relationships as edges.
  • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
  • Union-Find helps when connectivity updates are frequent.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
BFS / DFS traversal (this problem) O(V+E) O(V) Connectivity, flood fill
Dijkstra O((V+E)log V) O(V) Non-negative edge weights
Union-Find (DSU) O(α(n)) O(n) Dynamic connectivity
Topological sort O(V+E) O(V) DAG ordering, cycle detection

Solution

class Solution:
    def networkDelayTime(self, times, n, k):
        INF = float('inf')
        
        # Build adjacency matrix
        adj = [[INF] * n for _ in range(n)]
        
        for t in times:
            u = t[0] - 1
            v = t[1] - 1
            w = t[2]
            adj[u][v] = w
        
        dist = [INF] * n
        dist[k - 1] = 0
        
        visited = [False] * n
        
        for _ in range(n):
            minDist = INF
            u = -1
            
            for j in range(n):
                if not visited[j] and dist[j] < minDist:
                    minDist = dist[j]
                    u = j
            
            if u == -1:
                break
            
            visited[u] = True
            
            for v in range(n):
                if adj[u][v] != INF and dist[u] + adj[u][v] < dist[v]:
                    dist[v] = dist[u] + adj[u][v]
        
        ans = max(dist)
        
        return -1 if ans == INF else ans

Solution Explanation

Approach: BFS / DFS traversal (this problem)

Key idea: 1. Dijkstra’s Algorithm: Optimal for single-source shortest paths with non-negative weights

How the code works:

  1. Dijkstra’s Algorithm: Optimal for single-source shortest paths with non-negative weights
    • Adjacency matrix: Better for dense graphs (O(n²) time)
    • Adjacency list + min-heap: Better for sparse graphs (O((n+m)log n) time) - This is already optimal!
    • Model entities as nodes and relationships as edges.
    • Pick traversal (BFS/DFS) or shortest-path (Dijkstra) based on weights.
    • Union-Find helps when connectivity updates are frequent.

Walkthrough — input times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2, expected output 2:

The signal starts at node 2. At time 0, node 2 receives the signal. At time 1, nodes 1 and 3 receive the signal. At time 2, node 4 receives the signal. So the minimum time for all nodes to receive the signal is 2.

Algorithm Breakdown:

  1. Build Adjacency Matrix: Create n×n matrix where adj[i][j] represents edge weight from node i to node j, initialized with LLONG_MAX
  2. Initialize: Set dist[k-1] = 0 (source node), all others to LLONG_MAX
  3. Dijkstra’s Algorithm: For n iterations:
    • Find unvisited node u with minimum distance (linear scan)
    • Mark u as visited
    • Relax edges: Update distances to all neighbors of u if a shorter path is found
  4. Result: Return maximum distance, or -1 if any node is unreachable

Why This Works:

  • Dijkstra’s Property: Always processes the node with minimum distance first
  • Greedy Choice: Once a node is processed, its distance is final (non-negative weights guarantee this)
  • Relaxation: Updates distances to neighbors if a shorter path is found
  • Early Termination: If u == -1, all remaining nodes are unreachable, so we can break early

Solution 1 (Adjacency Matrix):

  • Time Complexity: O(n²) - For each of n nodes, scan all n nodes to find minimum
  • Space Complexity: O(n²) - Adjacency matrix

Solution 2 (Adjacency List + BFS):

  • Time Complexity: O(n*m) worst case - May process nodes multiple times
  • Space Complexity: O(n+m) - Adjacency list and queue

Solution 3 (Adjacency List + Min-Heap):

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Dijkstra’s Algorithm: Optimal for single-source shortest paths with non-negative weights
  2. Data Structure Choice:
    • Adjacency matrix: Better for dense graphs (O(n²) time)
    • Adjacency list + min-heap: Better for sparse graphs (O((n+m)log n) time) - This is already optimal!
  3. Maximum Distance: The answer is the maximum shortest distance, not the sum
  4. Unreachable Detection: Check if any distance remains LLONG_MAX
  5. Lazy Deletion: In min-heap version, skip outdated entries (if(dist[x] < time) continue) - this avoids expensive decrease-key operations
  6. BFS Limitation: BFS with a regular queue does NOT work correctly for weighted graphs - always use Dijkstra’s algorithm for shortest paths with weights
  7. Min-Heap Implementation: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> creates a min-heap where the smallest distance is at the top

References

Template Reference