Dijkstra’s Algorithm || Priority Queue || BFS || Explanation || Complexities
IntuitionWe need to determine the shortest time required for a signal to reach all nodes in a network. This problem is similar to finding the shortest path in a
## **Intuition**
We need to determine the shortest time required for a signal to reach all nodes in a network. This problem is similar to finding the **shortest path** in a weighted graph, where each edge represents the travel time.

The best approach to solve this problem is **Dijkstra’s Algorithm**, which efficiently finds the shortest path from a single source to all other nodes.

---

## **Approach**
1. **Graph Representation:**  
   - Convert the list of `times` into an **adjacency list**, where each node stores its neighbors and the corresponding travel time.
   - Since node numbers start from `1` to `n`, we use **1-based indexing**.

2. **Dijkstra’s Algorithm with Min-Heap (Priority Queue):**  
   - Use a **min-heap (priority queue)** to always process the node with the **smallest known delay** first.
   - Start from node `k`, initializing its delay to `0`.
   - Maintain a `network[]` array to store the **shortest time** to reach each node, initialized to `∞` (a large value).

3. **Process Nodes Efficiently:**  
   - Extract the node with the **smallest current delay** from the heap.
   - Update its neighbors if a **shorter** travel time is found.
   - Push the updated node into the heap for further processing.

4. **Find the Maximum Time:**  
   - Once all reachable nodes are processed, the **maximum value** in `network[]` gives the total delay time.
   - If any node remains `∞`, return `-1` as it's **not reachable**.

---

## **Algorithm Name**
This problem is solved using **Dijkstra’s Algorithm** with a **Min-Heap (Priority Queue)** for efficiency.

---

## **Complexity Analysis**
### **Time Complexity:**
- **Graph Construction:** \(O(E)\), where \(E\) is the number of edges.
- **Dijkstra’s Algorithm:**
  - Each node is processed once: \(O(N)\).
  - Each edge is relaxed once: \(O(E)\).
  - The priority queue operations take \(O(log N)\).
- **Overall Complexity:** O((N + E) log N), where \(N\) is the number of nodes and \(E\) is the number of edges.

### **Space Complexity:**
- **Adjacency list storage:** \(O(N + E)\).
- **Priority queue storage:** \(O(N)\).
- **Distance array:** \(O(N)\).
- **Overall Complexity:** \(O(N + E)\).

---

## **Edge Cases Considered**
✅ **Disconnected Nodes:** If any node is unreachable, return `-1`.  
✅ **Single Node Case:** If `n == 1`, return `0`.  
✅ **All Nodes Connected:** The algorithm efficiently finds the shortest delay time.  
✅ **Multiple Paths:** The algorithm correctly updates nodes only when a shorter path is found.  

This ensures the solution is **robust and efficient** for all cases. 🚀


# Code
```cpp []
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // Create adjacency list representation of the graph
        vector<vector<pair<int, int>>> adj(n + 1); // Using 1-based indexing

        for (const auto& time : times)
            adj[time[0]].push_back({time[1], time[2]});

        // Min-heap (priority queue) to always process the shortest known path first
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, k}); // {current time, current node}

        // Distance array to store the shortest time to each node
        vector<int> network(n + 1, INT_MAX);
        network[k] = 0;

        while (!pq.empty()) {
            auto [cur_time, cur] = pq.top();
            pq.pop();

            // Explore all adjacent nodes
            for (const auto& [new_cur, weight] : adj[cur]) {
                int new_time = cur_time + weight;

                if (new_time < network[new_cur]) {
                    network[new_cur] = new_time;
                    pq.push({new_time, new_cur});
                }
            }
        }

        // Find the maximum delay time among all reachable nodes
        int min_time = 0;
        for (int i = 1; i <= n; i++) {
            if (network[i] == INT_MAX) return -1; // If any node is unreachable
            min_time = max(min_time, network[i]);
        }

        return min_time;
    }
};
```
```java []
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency list representation of the graph
        ArrayList<ArrayList<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++)  // Using 1-based indexing
            adj.add(new ArrayList<>());

        // Fill adjacency list with edges
        for (int[] time : times)
            adj.get(time[0]).add(new int[]{time[1], time[2]}); 

        // Min-heap (priority queue) to always process the shortest known path first
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, k}); // {current time, current node}

        // Distance array to store the shortest time to each node
        int[] network = new int[n + 1];
        Arrays.fill(network, Integer.MAX_VALUE);
        network[k] = 0;

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int cur_time = top[0], cur = top[1];

            // Explore all adjacent nodes
            for (int[] time : adj.get(cur)) {
                int new_cur = time[0];
                int new_time = cur_time + time[1];

                if (new_time < network[new_cur]) {
                    network[new_cur] = new_time;
                    pq.add(new int[]{new_time, new_cur});
                }
            }
        }

        // Find the maximum delay time among all reachable nodes
        int min_time = 0;
        for (int i = 1; i <= n; i++) {
            if (network[i] == Integer.MAX_VALUE) return -1; // If any node is unreachable
            min_time = Math.max(min_time, network[i]);
        }

        return min_time;
    }
}
```
``` python []
class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Create adjacency list representation of the graph
        adj = {i: [] for i in range(1, n + 1)}  # Using 1-based indexing

        for u, v, w in times:
            adj[u].append((v, w))

        # Min-heap (priority queue) to always process the shortest known path first
        pq = [(0, k)]  # (current time, current node)
        network = {i: float('inf') for i in range(1, n + 1)}
        network[k] = 0

        while pq:
            cur_time, cur = heapq.heappop(pq)

            # Explore all adjacent nodes
            for new_cur, weight in adj[cur]:
                new_time = cur_time + weight

                if new_time < network[new_cur]:
                    network[new_cur] = new_time
                    heapq.heappush(pq, (new_time, new_cur))

        # Find the maximum delay time among all reachable nodes
        max_time = max(network.values())
        return max_time if max_time != float('inf') else -1
```
['Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'C++', 'Java', 'Python3']