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 is as follows:

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

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 is as follows:

1 --> 2 (1 unit time)

The minimum time to reach all nodes from node 1 is 1.

Steps

1. Build the graph: Represent the network as an adjacency list. Each node will have a list of its neighbors and the corresponding edge weights.
2. Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest paths from the starting node k to all other nodes. Dijkstra's algorithm is a greedy algorithm that iteratively finds the shortest path to each node.
3. Result: After Dijkstra's algorithm completes, the distance array will contain the shortest time to reach each node from node k. The maximum value in this array represents the maximum time to reach any node. If any node remains unreachable (distance is Integer.MAX_VALUE), it means it's impossible to reach all nodes, and we return -1.

Explanation

Dijkstra's algorithm works by maintaining a set of visited nodes and a priority queue to efficiently select the node with the shortest distance. In each iteration, it selects the unvisited node with the smallest distance and updates the distances of its neighbors if a shorter path is found.

Code

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Build adjacency list
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        // Dijkstra's algorithm
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k}); // {distance, node}

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int u = curr[1];

            if (d > dist[u]) continue; // Optimization: Skip if already found shorter path

            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                int weight = edge[1];
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        // Find maximum distance
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // Unreachable node
            maxDist = Math.max(maxDist, dist[i]);
        }

        return maxDist;
    }
}

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (nodes). This is due to the use of Dijkstra's algorithm with a priority queue.
• Space Complexity: O(V + E), primarily due to the adjacency list representation of the graph and the distance array. The priority queue's size is at most V in the worst case.