Network Delay Time
You are given a network of n nodes represented as an adjacency list of edgesQuestion and saidQuestion and said to be connected if there is a path between every pair of nodes. The time taken to send a signal from node k to node i is given by times[i][0] = k and times[i][1] = i. Given a signal sent from node k, find the minimum time it takes for all nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.
Constraints:
- 1 <= n <= 100
- 1 <= k <= n
- 1 <= times.length <= 6000
- times[i].length == 2
- 1 <= times[i][0] <= n
- 1 <= times[i][1] <= n
- 1 <= times[i][2] <= 100
Examples:
Input: [[2,1,1],[2,3,1],[3,4,1]] and n = 4 and k = 2
Output: 2
Explanation: The signal is sent from node 2. The signal reaches node 1 after 1 millisecond and node 3 after 1 millisecond. The signal reaches node 4 after 2 milliseconds.
Solutions
Dijkstra's Algorithm
We use Dijkstra's algorithm to find the shortest path from node k to all other nodes. We maintain a priority queue of nodes to be processed, where the priority is the current shortest distance from node k to the node. We also maintain an array dist to store the shortest distance from node k to each node. We start by initializing dist[k] to 0 and adding node k to the priority queue. Then, we repeatedly extract the node with the minimum distance from the priority queue and update the distances of its neighbors. If the distance to a neighbor is updated, we add the neighbor to the priority queue. We repeat this process until the priority queue is empty. Finally, we find the maximum distance in the dist array. If the maximum distance is infinity, it means that some nodes are unreachable from node k, so we return -1. Otherwise, we return the maximum distance.
function networkDelayTime(times, n, k) {
let g = Array.from({
length: n + 1 }
, () => []);
for (let [u, v, w] of times) {
g[u].push([v, w]);
}
let dist = Array(n + 1).fill(Infinity);
dist[k] = 0;
let pq = [[k, 0]];
while (pq.length) {
let [u, d] = pq.shift();
if (d > dist[u]) continue;
for (let [v, w] of g[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
pq.push([v, dist[v]]);
pq.sort((a, b) => a[1] - b[1]);
}
}
let max = Math.max(...dist.slice(1));
return max === Infinity ? -1 : max;
}Follow-up:
What if the graph is directed and we want to find the minimum time it takes for all nodes to receive the signal?
