90.1 (Approach 1: Dijkstra's algorithm) | O(E * log V)✅ | Python & C++(Step by step explanation)✅
Intuition\nThe problem can be approached using Dijkstra\'s algorithm, which is a popular algorithm for finding the shortest paths between nodes in a graph. Here
# Intuition\nThe problem can be approached using Dijkstra\'s algorithm, which is a popular algorithm for finding the shortest paths between nodes in a graph. Here, each node represents a point in the network, and the edges represent the time it takes for a signal to travel between two points.\n\n# Approach\n1. **Build the Graph**:\n   - In this step, we convert the given list of times into a graph representation. Each node in the network is represented as a key in the `edges` dictionary, and its value is a list of tuples containing the target node and the time it takes to travel from the source node to the target node.\n   - This step is crucial because it helps us efficiently traverse the network and compute the minimum time for all nodes to receive the signal. By organizing the data into a graph structure, we can easily access the neighboring nodes of any given node.\n\n2. **Apply Dijkstra\'s Algorithm**:\n   - Dijkstra\'s algorithm is a popular method for finding the shortest path from a source node to all other nodes in a weighted graph. Since our problem involves finding the minimum time for all nodes to receive the signal from a given source node, Dijkstra\'s algorithm is a suitable choice.\n   - We utilize a min-heap to efficiently select the node with the minimum time to propagate the signal. This ensures that we explore the paths with the shortest cumulative time first, leading to an optimal solution.\n\n3. **Process Nodes**:\n   - In each iteration of the algorithm, we pop the node with the minimum time from the min-heap. This node represents the next node to be processed.\n   - We check if the node has already been visited. If it has, we skip processing it further to avoid revisiting nodes unnecessarily.\n   - If the node has not been visited, we mark it as visited and update the current time to the time taken to reach this node. This ensures that we keep track of the cumulative time as we traverse the network.\n\n4. **Update Neighbors**:\n   - For each neighbor of the current node, we calculate the total time taken to reach that neighbor by adding the time taken to travel from the current node to the neighbor to the current time.\n   - We then push this updated time and the neighbor node into the min-heap if the neighbor node has not been visited yet. This allows us to explore all possible paths from the current node efficiently.\n\n5. **Check Completeness**:\n   - After processing all nodes, we check if all nodes have been visited. If all nodes have been visited, it means that the signal has successfully reached all nodes in the network.\n   - In this case, we return the current time as the minimum time taken for all nodes to receive the signal.\n   - If not all nodes have been visited, it indicates that some nodes could not receive the signal within the given network structure. In such a scenario, we return -1 to signify that it is impossible for all nodes to receive the signal.\n\n# Example\n![image.png](https://assets.leetcode.com/users/images/60784b10-a4e0-4c07-8331-dcd3288fff04_1708253588.8262053.png)\n\n![image.png](https://assets.leetcode.com/users/images/712a1f9a-05e4-49c2-a497-bcbcceee71c2_1708253727.9923072.png)\n\n![image.png](https://assets.leetcode.com/users/images/4a364cf4-8b1b-4fce-be43-ae2178f4e6ac_1708253821.8643305.png)\n\n![image.png](https://assets.leetcode.com/users/images/8907165a-56cb-47e0-8131-05155a27db3e_1708253940.732096.png)\n\n![image.png](https://assets.leetcode.com/users/images/bd4081b1-b478-450e-bb1f-99ac94b14795_1708254006.2043028.png)\n\n![image.png](https://assets.leetcode.com/users/images/8ea17801-5a19-46b7-bac7-22b0f7b1e275_1708254077.641654.png)\n\n# Complexity\n- Time complexity: \\(O(E * log V)\\), where \\(E\\) is the number of edges and \\(V\\) is the number of vertices (nodes) in the graph. Dijkstra\'s algorithm has a time complexity of \\(O(E \\log V)\\) when implemented using a min-heap.\n- Space complexity: \\(O(V + E)\\) for storing the graph and the min-heap.\n\n## Python Implementation:\n```python\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n        # Create a defaultdict to store the adjacency list representation of the graph\n        edges = collections.defaultdict(list)\n        \n        # Populate the adjacency list with the given edges and weights\n        for u, v, w in times:\n            edges[u].append((v, w))\n\n        # Initialize a minHeap with (0, k), where k is the starting node and 0 is the distance to k\n        minHeap = [(0, k)]\n        \n        # Initialize a set to keep track of visited nodes\n        visit = set()\n        \n        # Initialize the time variable to track the maximum time taken to reach all nodes\n        t = 0\n        \n        # While there are elements in the minHeap\n        while minHeap:\n            # Pop the node with the minimum distance from the minHeap\n            w1, n1 = heapq.heappop(minHeap)\n            \n            # If the node has been visited, continue to the next iteration\n            if n1 in visit:\n                continue\n            \n            # Mark the current node as visited\n            visit.add(n1)\n            \n            # Update the time to the current distance\n            t = w1\n\n            # Iterate over the neighbors of the current node\n            for n2, w2 in edges[n1]:\n                # If the neighbor has not been visited yet\n                if n2 not in visit:\n                    # Add the neighbor to the minHeap with updated distance\n                    heapq.heappush(minHeap, (w1 + w2, n2))\n        \n        # If all nodes have been visited, return the maximum time taken\n        return t if len(visit) == n else -1\n```\n\n## C++ Implementation:\n```c++\nclass Solution {\npublic:\n    int networkDelayTime(vector<vector<int>>& times, int n, int k) {\n        // Create an adjacency list to represent the graph\n        vector<pair<int, int>> adj[n + 1];\n        \n        // Populate the adjacency list with the given edges and weights\n        for (int i = 0; i < times.size(); i++) {\n            int source = times[i][0];\n            int dest = times[i][1];\n            int time = times[i][2];\n            adj[source].push_back({time, dest});\n        }\n        \n        // Initialize a vector to store the time taken to receive signals at each node\n        vector<int> signalReceiveTime(n + 1, INT_MAX);\n        \n        // Initialize a priority queue to keep track of nodes with the minimum time\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        \n        // Push the starting node k with time 0 into the priority queue\n        pq.push({0, k});\n        \n        // Update the signalReceiveTime of the starting node to 0\n        signalReceiveTime[k] = 0;\n        \n        // While the priority queue is not empty\n        while (!pq.empty()) {\n            // Extract the node with the minimum time from the priority queue\n            int currNodeTime = pq.top().first;\n            int currNode = pq.top().second;\n            pq.pop();\n            \n            // If the current time to reach the node is greater than the recorded time, skip\n            if (currNodeTime > signalReceiveTime[currNode]) {\n                continue;\n            }\n            \n            // Iterate over the neighbors of the current node\n            for (int i = 0; i < adj[currNode].size(); i++) {\n                pair<int, int> edge = adj[currNode][i];\n                int time = edge.first;\n                int neighborNode = edge.second;\n                \n                // If the time to reach the neighbor node through the current node is less than the recorded time\n                if (signalReceiveTime[neighborNode] > currNodeTime + time) {\n                    // Update the time and push the neighbor node into the priority queue\n                    signalReceiveTime[neighborNode] = currNodeTime + time;\n                    pq.push({signalReceiveTime[neighborNode], neighborNode});\n                }\n            }\n        }\n        \n        // Find the maximum time taken to reach all nodes\n        int result = INT_MIN;\n        for (int i = 1; i <= n; i++) {\n            result = max(result, signalReceiveTime[i]);\n        }\n        \n        // If any node cannot receive a signal, return -1\n        if (result == INT_MAX) {\n            return -1;\n        }\n        return result;\n    }\n};\n```\n\n\n# Please upvote the solution if you understood it.\n![1_3vhNKl1AW3wdbkTshO9ryQ.jpg](https://assets.leetcode.com/users/images/0161dd3b-ad9f-4cf6-8c43-49c2e670cc21_1699210823.334661.jpeg)\n
['Graph', 'Heap (Priority Queue)', 'C++', 'Python3']