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

java class Solution { public int networkDelayTime(int[][] times, int n, int k) { List<List<int[]>> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) graph.add(new ArrayList<>()); for (int[] t : times) graph.get(t[0]).add(new int[] {t[1], t[2]}); int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[k] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); pq.offer(new int[] {0, k}); while (!pq.isEmpty()) { int[] cur = pq.poll(); int d = cur[0], u = cur[1]; if (d > dist[u]) continue; for (int[] e : graph.get(u)) { int v = e[0], w = e[1]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(new int[] {dist[v], v}); } } } int ans = 0; for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) return -1; ans = Math.max(ans, dist[i]); } return 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