City Network Signal Time

This problem asks us to find the minimum time it takes for a signal sent from node k to reach all other nodes in a network. If it's impossible for all nodes to receive the signal, return -1.

Naive Solution: Brute Force

A brute-force approach would be to explore all possible paths from the starting node k and keep track of the minimum time it takes to reach each node. We can use a recursive Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph. However, this approach can be inefficient, especially if there are cycles in the graph, as we might end up revisiting nodes multiple times.

1. Initialize a dist array where dist[i] represents the shortest time to reach node i from k. Initialize all values to infinity except dist[k] which will be zero.
2. Use DFS or BFS to traverse the graph, updating dist whenever a shorter path to a node is found.
3. After traversal, if any value in dist is still infinity, return -1.
4. Otherwise, return the maximum value in the dist array.

Big O Complexity

• Time Complexity: O(V * E), where V is the number of vertices (nodes) and E is the number of edges, since we might have to potentially explore all the paths.
• Space Complexity: O(V), where V is the number of vertices. This is due to the dist array and the space used by the recursion stack or queue depending if you choose to implement with DFS or BFS

Optimal Solution: Dijkstra's Algorithm

A more efficient approach is to use Dijkstra's algorithm, which is designed to find the shortest path from a source node to all other nodes in a weighted graph. Dijkstra's algorithm uses a priority queue to efficiently explore the nodes with the smallest known distance first.

1. Build an adjacency list representation of the graph where the key is the source node, and the value is a list of (neighbor, weight) pairs representing the edges.
2. Initialize a dist array to store the shortest distance from the source node k to each node, setting all distances to infinity initially.
3. Set the distance from k to itself to 0.
4. Use a min-priority queue to store nodes and their distances. The priority queue should be ordered by distance.
5. 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 the calculated distance is less than the current distance to v:
       • Update the distance to v in the dist array.
       • Add v to the priority queue with the new distance.
6. After the algorithm finishes, check if all nodes are reachable. If any node has a distance of infinity, it means it's not reachable, and we return -1.
7. Otherwise, return the maximum distance in the dist array, which represents the minimum time it takes for all nodes to receive the signal.

Edge Cases

• If the graph is disconnected, some nodes might not be reachable from the source node k. In this case, the algorithm should return -1.
• If the graph contains negative edge weights, Dijkstra's algorithm will not work correctly. Bellman-Ford's algorithm must be used instead. Based on constraints, there are no negative weights.
• If the input times is empty and n is greater than 1, then it is impossible to reach all nodes, so return -1. If n is 1, return 0.

Big O Complexity

• Time Complexity: O(E + V log V), where V is the number of vertices (nodes) and E is the number of edges. This is because each edge is visited at most once, and priority queue operations take O(log V) time.
• Space Complexity: O(V + E), where V is the number of vertices and E is the number of edges. This is due to the space required to store the adjacency list and the dist array.

Python Code

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, w in graph[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

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