743. Network Delay Time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
Example 2:
Example 3:
Constraints:
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Solution:
class Solution {
// Adjacency list
Map<Integer, List<Pair<Integer, Integer>>> adj = new HashMap<>();
//The adjacency list (adj) is a map where the key is a node, and the value is a list of pairs. Each pair contains the travel time to a neighboring node and the neighboring node itself.
// adj: , <>
// 2, <1, 1> [2]-1->[1]
// 2, <1, 3> [2]-1->[3]
// 3, <1, 4> [3]-1->[4]
public int networkDelayTime(int[][] times, int n, int k) {
for (int[] time : times){ // [2,1,1]; [2,3,1];[3,4,1]
int source = time[0]; // 2 // 2,
int dest = time[1]; // 1 // 3
int travelTime = time[2]; // 1 // 1
adj.putIfAbsent(source, new ArrayList<>());
adj.get(source).add(new Pair(travelTime, dest));
}
// Iterate through the times array to build the adjacency list. For each time array, extract the source node, destination node, and travel time. Add these to the adjacency list.
int[] signalReceivedAt = new int[n + 1];
// [4+ 1] =[5]
// 0 1 2 3 4
//[0,0,0,0,0]
Arrays.fill(signalReceivedAt, Integer.MAX_VALUE);
// 0 1 2 3 4
//[-,-,-,-,-]
// Initialize an array signalReceivedAt to store the minimum time at which each node receives the signal. Initially, set all values to Integer.MAX_VALUE (a large number representing infinity).
dijkstra(signalReceivedAt, k, n);
int result = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++){
result = Math.max(result, signalReceivedAt[i]);
}
if (result == Integer.MAX_VALUE){
return -1;
}else{
return result;
}
// Find the maximum value in the signalReceivedAt array, which represents the time it takes for the signal to reach the furthest node. If this value is Integer.MAX_VALUE, it means not all nodes are reachable, so return -1. Otherwise, return the maximum delay time.
}
private void dijkstra(int[] signalReceivedAt, int k, int n){
// PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer, Integer>>(
// Comparator.comparing(Pair::getKey)
// );
// PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer, Integer>>(
// new Comparator<Pair<Integer,Integer>>(){
// @Override
// public int compare(Pair<Integer, Integer> p1, Pair<Integer,Integer> p2){
// return Integer.compare(p1.getKey(), p2.getKey());
// }
// }
// );
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer, Integer>>(
new Comparator<Pair<Integer,Integer>>(){
@Override
public int compare(Pair<Integer, Integer> p1, Pair<Integer,Integer> p2){
if (p1.getKey() < p2.getKey()){
return -1;
}else if (p1.getKey() > p2.getKey()){
return 1;
}else{
return 0;
}
}
}
);
pq.add(new Pair(0, k)); // pq: [0, 2]
signalReceivedAt[k] = 0; //
// 0 1 2 3 4
//[-,-,0,-,-]
// Use a priority queue (pq) to always process the node with the smallest known distance. Initialize it with the starting node k and set the signal received time for k to 0.
while(!pq.isEmpty()){
// pq: <1,3>
Pair<Integer, Integer> topPair = pq.poll(); // [0,2];// <1,1> // <1,3>
// cost, source
int currNode = topPair.getValue();// 2 // 1// 3
int currNodeTime = topPair.getKey(); // 0 // 1 // 1
if (currNodeTime > signalReceivedAt[currNode]){
continue;
}
// adj: , <>
// 2, <1, 1> [2]-1->[1]
// 2, <1, 3> [2]-1->[3]
// 3, <1, 4> [3]-1->[4]
if (!adj.containsKey(currNode)){
continue;
}
// 2, <1, 1> [2]-1->[1]
// 2, <1, 3> [2]-1->[3]
// 更新邻居节点的信号接收时间，如果找到更短的路径
for (Pair<Integer, Integer> edge : adj.get(currNode)){ // <1, 1>, <1,3>,
int time = edge.getKey(); // 1 // 1 // 1
int neighborNode = edge.getValue(); // 1// 3
// 0 1 2 3 4
//[-,1,0,1,-]
if (signalReceivedAt[neighborNode] > currNodeTime + time){
// signalReceivedAt[1] = - > 0 + 1 = 1
// signalReceivedAt[3] = - > 0 + 1 = 1
//
signalReceivedAt[neighborNode] = currNodeTime + time;
pq.add(new Pair(signalReceivedAt[neighborNode], neighborNode));
// <1, 1>, <1, 3>
}
}
}
// While the priority queue is not empty, process each node by updating the signal received time for its neighbors if a shorter path is found. Add these neighbors to the priority queue to continue processing.
}
}
// TC: O(n+elogn)
// SC: O(n)
After solving this using Dijkstra−algorithm you can implement this in the following questions 787. Cheapest Flights Within K Stops 778. Swim in Rising Water 815. Bus Routes 1091. Shortest Path in Binary Matrix 1631. Path With Minimum Effort 2812. Find the Safest Path in a Grid 2642. Design Graph With Shortest Path Calculator