✅BEST | GRAPH | JAVA | Explained🔥🔥🔥
Intuition
The problem requires us to determine the time it takes for a signal to reach all nodes in a directed weighted graph. Since this is a shortest path pro
**Intuition**
The problem requires us to determine the time it takes for a signal to reach all nodes in a directed weighted graph. Since this is a shortest path problem where we need to find the minimum time from a source node to all other nodes, Dijkstra's algorithm is a natural fit because it efficiently finds the shortest path in a graph with positive weights.

**Approach**
**Graph Representation:**

We represent the graph using an adjacency list stored in a HashMap<Integer, List<int[]>>.
Each node maps to a list of integer arrays [neighbor, travel_time], where neighbor is the destination node and travel_time is the time taken to reach it.
Dijkstra's Algorithm (Priority Queue / Min-Heap):

We use a Priority Queue (Min-Heap) to always expand the node with the smallest known time first.
Start with the given node k with time 0 (i.e., pq.offer(new int[]{k, 0})).
Maintain a distance map (dist) to store the shortest time to reach each node.
Process nodes in the priority queue:
Extract the node with the smallest recorded time.
If it has already been processed, skip it.
Otherwise, update its shortest known time and push its neighbors to the queue.
Repeat until all nodes are visited or the queue is empty.
Final Result Calculation:

If we have visited all n nodes, return the maximum time among all shortest paths (Collections.max(dist.values())).
If some nodes are unreachable, return -1.

**Complexity Analysis**
**Time Complexity:**
Constructing the adjacency list takes O(E) time, where E is the number of edges.
The priority queue operations (insertion/removal) take O(log V) time, where V is the number of nodes.
Since each node is processed once and each edge is relaxed once, the total time complexity is O((V + E) log V).
**Space Complexity:**
O(V + E) for storing the graph adjacency list.
O(V) for the priority queue (since at most all nodes can be in the queue at once).
O(V) for the dist map.
Overall, the space complexity is O(V + E).

# Code
```java []
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency list for graph representation
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) graph.put(i, new ArrayList<>());
        
        for (int[] time : times) {
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        // Priority Queue (Min-Heap) for Dijkstra's Algorithm
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{k, 0}); // Start with the source node
        
        Map<Integer, Integer> dist = new HashMap<>();
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll(); // Get the node with the smallest time
            int node = curr[0], time = curr[1];

            if (dist.containsKey(node)) continue; // Skip if already visited
            
            dist.put(node, time);
            
            for (int[] neighbor : graph.get(node)) {
                int nextNode = neighbor[0], nextTime = neighbor[1];
                if (!dist.containsKey(nextNode)) {
                    pq.offer(new int[]{nextNode, time + nextTime});
                }
            }
        }
        
        if (dist.size() != n) return -1; // If not all nodes are reached, return -1
        return Collections.max(dist.values()); // Return the maximum time taken
    }
}
```
['Java']