Problem Statement

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.

Additional information

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

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

Explanation: The signal is sent from node 2, but there is no directed edge from node 2 to node 1. Node 1 will never receive the signal.

Bellman-Ford Algorithm

Intuition

To find the time it takes for the signal to reach every node, we essentially need to find the shortest path from our starting node k to every other node in the network. The maximum of these shortest paths will be our answer, because all signals travel simultaneously.

The Bellman-Ford algorithm is a classic way to find single-source shortest paths. We initialize an array holding the minimum distance to every node as infinity, except for our starting node k, which is 0.

Then, we iterate n - 1 times. In each iteration, we loop through every single edge in the network. If the time to reach the source node plus the travel time of the edge is less than the current recorded time to reach the target node, we update the target node's time (this is called "relaxing" the edge).

Algorithm

1. Initialize a distances array of size n + 1 (since nodes are 1-indexed) filled with infinity (float("inf")).
2. Set the distance to the starting node k to 0: distances[k] = 0.
3. Run a loop n - 1 times.
4. Inside the loop, iterate through every u, v, w in times.
5. If distances[u] + w < distances[v], update distances[v] = distances[u] + w.
6. After the loops finish, check the maximum value in the distances array (ignoring index 0).
7. If the maximum value is still infinity, it means at least one node was unreachable. Return -1. Otherwise, return that maximum value.

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    # Initialize distances to infinity
    distances = [float("inf")] * (n + 1)
    distances[k] = 0
    
    # Relax edges n - 1 times
    for _ in range(n - 1):
        for u, v, w in times:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
                
    # Find the maximum time it took to reach any node
    max_time = max(distances[1:])
    
    # If any node has infinity distance, it's unreachable
    return max_time if max_time != float("inf") else -1

Time & Space Complexity

• Time complexity: O(N * E)

• Reason: We iterate over all E edges exactly N - 1 times, where N is the number of nodes.

• Space complexity: O(N)

• Reason: We only use a 1D array of size N + 1 to store the distances.

Dijkstra's Algorithm (Min-Heap) - Optimal

Intuition

While Bellman-Ford is simple, it blindly checks every edge repeatedly. We can solve this much faster using Dijkstra's Algorithm.

Dijkstra's algorithm acts like the signal spreading out dynamically. We keep a Min-Heap (Priority Queue) that always gives us the node with the shortest current travel time.

We start by putting our source node k into the heap with a time of 0. When we pop a node, we permanently add its time to a visited set. Then, we look at all its neighboring nodes. We add the time it took to reach our current node plus the edge weight to reach the neighbor, and push that new total time into the heap. Because the Min-Heap always processes the shortest paths first, the very first time we pop a node, we are guaranteed it is the absolute fastest way to reach it!

Algorithm

1. Build an adjacency list adj where adj[u] contains tuples of (neighbor_v, travel_time_w).
2. Initialize a min_heap with the starting node: [(0, k)] representing (current_time, current_node).
3. Initialize a visited set to keep track of nodes we have securely reached.
4. Initialize a total_time variable to 0.
5. While the min_heap is not empty:

• Pop the time, node with the smallest time.
• If node is already in visited, skip it (continue).
• Add node to visited.
• Update total_time to be the current time (since the heap pops in increasing order, the last popped valid node will dictate the total maximum time).
• Iterate through the neighbors of node. If a neighbor is not in visited, push (time + weight, neighbor) into the min_heap.

6. If len(visited) == n, we reached all nodes! Return total_time. Otherwise, return -1.

def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
        
    # Min-heap stores tuples of (time, node)
    min_heap = [(0, k)]
    visited = set()
    total_time = 0
    
    while min_heap:
        time, node = heapq.heappop(min_heap)
        
        # If we already locked in the shortest path for this node, skip
        if node in visited:
            continue
            
        visited.add(node)
        total_time = time
        
        # Explore neighbors
        for neighbor, weight in adj[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (time + weight, neighbor))
                
    return total_time if len(visited) == n else -1

Time & Space Complexity

• Time complexity: O(E log V)

• Reason: In the worst case, we might add every single edge (E) to the Min-Heap. Pushing and popping from a heap of size E takes O(log E) time. Since E <= V^2, log(E) is equivalent to log(V). Thus, the total time is O(E log V).

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space. The Min-Heap can hold up to O(E) elements, and the visited set holds up to O(V) elements.