City Network Signal Time

Problem Description

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] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> 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.

Brute Force Solution

A brute-force solution would involve exploring all possible paths from the source node k to all other nodes in the graph. We can perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to find paths. However, this approach would not guarantee the minimum time and could be inefficient due to exploring many non-optimal paths.

Complexity Analysis

• Time Complexity: O(V + E) where V is the number of vertices(nodes) and E is the number of edges. In the worst case, it might explore all possible paths which could be exponential.
• Space Complexity: O(V), due to the recursion stack or queue used in DFS/BFS.

Optimal Solution: Dijkstra's Algorithm

The optimal solution is to use Dijkstra's algorithm, which is designed to find the shortest paths from a single source node to all other nodes in a weighted graph. Here's how it works:

1. Initialization:
   • Create a distance array dist of size n, initialized with infinity for all nodes except the source node k, which is initialized with 0.
   • Create a min-priority queue (min-heap) to store nodes to visit, prioritized by their distance from the source.
2. Iteration:
   • While the priority queue is not empty:
     • Extract the node u with the smallest distance from the priority queue.
     • For each neighbor v of u:
       • Calculate the distance to v through u.
       • If this distance is smaller than the current distance to v:
         • Update dist[v] with the new smaller distance.
         • Add v to the priority queue (or update its priority if it's already in the queue).
3. Result:
   • After the algorithm finishes, the dist array contains the shortest distances from the source node k to all other nodes.
   • Find the maximum value in the dist array. If any value is still infinity, it means that some nodes are unreachable, and return -1. Otherwise, return the maximum distance.

Code Implementation (Python)

import heapq

def networkDelayTime(times, n, k):
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))

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

    pq = [(0, k)]  # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

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

Complexity Analysis

• Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices (nodes).
• Space Complexity: O(V + E), to store the graph, the distance array, and the priority queue.

Edge Cases

• If the graph is not connected, some nodes may not be reachable from the source node k. In this case, Dijkstra's algorithm will result in some distances remaining infinity, and the function should return -1.
• If k is not a valid node (e.g., k is less than 1 or greater than n), it may be good to raise an exception, but based on the problem constraints that case is excluded.
• If there are negative edge weights, Dijkstra's algorithm will not work correctly. However, based on the problem constraints this case is excluded.