grid47 Exploring patterns and algorithms
Aug 24, 2024
7 min read
Solution to LeetCode 743: Network Delay Time Problem
You are given a network of n nodes and a list of directed edges with travel times. You need to send a signal from a given node k. Return the minimum time it takes for all nodes to receive the signal, or return -1 if it is impossible.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of directed edges `times[i] = (ui, vi, wi)` representing the travel time from node `ui` to node `vi`, as well as the number of nodes `n` and the starting node `k`.
Example: times = [[1, 2, 1], [1, 3, 2], [3, 4, 1]], n = 4, k = 1
Constraints:
• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All (ui, vi) pairs are unique.
Output: Return the minimum time it takes for all `n` nodes to receive the signal, or return `-1` if it is impossible for all nodes to receive the signal.
Example: For times = [[1, 2, 1], [1, 3, 2], [3, 4, 1]], n = 4, k = 1, the output is 3.
Constraints:
Goal: Find the minimum time it takes for all nodes to receive the signal or determine if it is impossible.
Steps:
• Use a graph representation to model the nodes and edges with the travel times.
• Use Dijkstra's algorithm to find the shortest path from the starting node `k` to all other nodes.
• If all nodes are reachable, return the maximum time taken by the farthest node.
• If any node is unreachable, return `-1`.
Goal: The input graph has up to 100 nodes and 6000 edges. The graph is directed, and there are no multiple edges between any two nodes.
Steps:
• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• 0 <= wi <= 100
Assumptions:
• The network will be represented as a directed graph with unique edges.
• Input: For times = [[1, 2, 1], [1, 3, 2], [3, 4, 1]], n = 4, k = 1
• Explanation: By using Dijkstra's algorithm, we can calculate the shortest time for the signal to reach each node, and we find that the signal reaches all nodes in 3 units of time.
Approach: This problem can be solved using Dijkstra's algorithm to find the shortest path from the starting node to all other nodes in the graph.
Observations:
• We need to find the shortest time for a signal to reach all nodes from the starting node.
• The problem can be modeled as a shortest path problem in a weighted directed graph.
• Since the graph can have up to 6000 edges, Dijkstra's algorithm with a priority queue should be efficient enough.
Steps:
• Create a map to represent the directed graph with travel times.
• Use a priority queue to implement Dijkstra's algorithm for finding the shortest time from node `k` to all other nodes.
• For each node, update the shortest time to reach it and continue until all reachable nodes are processed.
• If any node is unreachable, return `-1`. Otherwise, return the maximum time it took to reach all nodes.
Empty Inputs:
• There will always be at least one node and one edge, so no empty graph cases.
Large Inputs:
• For large inputs (with up to 6000 edges), the solution should be optimized to handle the upper limits efficiently.
Special Values:
• If the starting node `k` is isolated or there are disconnected nodes, the function should return `-1`.
Constraints:
• Ensure that the algorithm works efficiently for graphs with up to 6000 edges.
intnetworkDelayTime(vector<vector<int>>& times, int n, int k) {
map<int, map<int, int>> mp;
for(int i =0; i < times.size(); i++) {
mp[times[i][0]][times[i][1]] = times[i][2];
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
vector<int> vis(n +1, 0);
pq.push(make_pair(0, k));
while(!pq.empty()) {
auto it = pq.top();
pq.pop();
if(vis[it.second]) continue;
vis[it.second] =true;
n--;
if(n ==0) return it.first;
if(mp.count(it.second))
for(auto [key, val]: mp[it.second]) {
pq.push(make_pair(val + it.first, key));
}
}
return-1;
}
1 : Function Declaration
intnetworkDelayTime(vector<vector<int>>& times, int n, int k) {
Function that computes the time it takes for all nodes to receive the signal starting from node 'k'.
2 : Variable Initialization
map<int, map<int, int>> mp;
This map stores the network connections where each node is mapped to another node with its travel time.
3 : Loop Setup
for(int i =0; i < times.size(); i++) {
Loop to iterate through the 'times' array and populate the map with edges (nodes and weights).
4 : Map Update
mp[times[i][0]][times[i][1]] = times[i][2];
Updating the map with the source node, destination node, and the travel time between them.
A priority queue to always process the node with the smallest time first.
6 : Visited Nodes Setup
vector<int> vis(n +1, 0);
A vector to track which nodes have been visited.
7 : Push Initial Node
pq.push(make_pair(0, k));
Push the starting node 'k' with an initial time of 0 into the priority queue.
8 : While Loop
while(!pq.empty()) {
While the priority queue is not empty, process each node.
9 : Extract Minimum
auto it = pq.top();
Extract the node with the smallest accumulated time from the priority queue.
10 : Pop from Queue
pq.pop();
Remove the top element (current node) from the priority queue.
11 : Skip Visited
if(vis[it.second]) continue;
Skip nodes that have already been visited to avoid unnecessary processing.
12 : Mark as Visited
vis[it.second] =true;
Mark the current node as visited.
13 : Decrement Nodes
n--;
Decrement the number of remaining nodes to be processed.
14 : Check Completion
if(n ==0) return it.first;
If all nodes are visited, return the accumulated time to reach the farthest node.
15 : Edge Traversal Check
if(mp.count(it.second))
Check if the current node has any outgoing edges.
16 : Process Neighbors
for(auto [key, val]: mp[it.second]) {
Iterate over all neighboring nodes of the current node.
17 : Push Neighbors to Queue
pq.push(make_pair(val + it.first, key));
Push the neighboring nodes into the priority queue with the updated accumulated time.
18 : Return Failure
return-1;
Return -1 if it's not possible to visit all nodes.
Best Case: O(E log V), where E is the number of edges and V is the number of nodes.
Average Case: O(E log V), as each edge and node is processed once.
Worst Case: O(E log V), where E is the number of edges and V is the number of nodes.
Description: The time complexity is O(E log V), where E is the number of edges and V is the number of nodes, due to the priority queue operations in Dijkstra's algorithm.
Best Case: O(V + E), for storing the graph and the priority queue.
Worst Case: O(V + E), where V is the number of nodes and E is the number of edges.
Description: The space complexity is O(V + E) due to the storage required for the graph and the priority queue.
