Network Delay Time medium

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] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

We want to find the minimum time it takes for a signal to travel from node k to all other nodes. If it is impossible, return -1.

Example 1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2

Explanation: The graph looks like this:

2 --> 1 (1)
2 --> 3 (1)
3 --> 4 (1)

The minimum time to reach all nodes from node 2 is 2 (2->3->4).

Example 2

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1

Explanation: The graph looks like this:

1 --> 2 (1)

The minimum time to reach all nodes from node 1 is 1 (1->2).

Steps

1. Build the graph: Represent the network as an adjacency list.
2. Initialize distances: Create a distance array dist of size n+1, where dist[i] represents the shortest distance from node k to node i. Initialize all distances to infinity, except dist[k] which is 0.
3. Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest paths from node k to all other nodes. This algorithm iteratively explores nodes, updating distances as shorter paths are found. A min-heap (priority queue) is used to efficiently select the node with the smallest distance.
4. Check for unreachable nodes: After Dijkstra's algorithm completes, check if any node's distance remains infinity. If so, it means that node is unreachable from node k, and we return -1.
5. Find the maximum distance: Otherwise, find the maximum distance among all nodes. This represents the maximum time it takes to reach all nodes from k.

Explanation

Dijkstra's algorithm is a greedy algorithm that finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It works by iteratively selecting the node with the smallest distance from the source and updating the distances of its neighbors. The use of a min-heap optimizes the selection of the node with the minimum distance.

The algorithm terminates when all nodes have been visited or when the min-heap is empty. If any node remains unvisited (meaning its distance is still infinity), it indicates that the node is unreachable from the source.

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_dist = max(dist.values())
    return max_dist if max_dist != float('inf') else -1

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices. This is due to the use of Dijkstra's algorithm with a min-heap.
• Space Complexity: O(V + E), due to the adjacency list representation of the graph and the distance array. The heap's space complexity is also bounded by O(V).