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 {
public int networkDelayTime(int[][] times, int n, int k) {
int result = Integer.MIN_VALUE;
// Create the graph as an adjacency list
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] time : times){
int source = time[0];
int target = time[1];
int weight = time[2];
graph.putIfAbsent(source, new ArrayList<>());
graph.get(source).add(new int[]{target, weight});
}
int[] dist = dijkstra(graph, n, k);
for (int i = 1; i < dist.length; i++){
result = Math.max(result, dist[i]);
}
if (result == Integer.MAX_VALUE){
return -1;
}else{
return result;
}
}
private int[] dijkstra(Map<Integer, List<int[]>> graph, int n, int source){
// Step 1: Initialize-Single-Source
int[] dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE); // // Set all distances to infinity
dist[source] = 0; // // Distance to the source node is 0
// Step 2: Create the set S (visited)
Set<Integer> visited = new HashSet<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
// minHeap
pq.offer(new int[]{source, 0}); // Distance to the source node is
// {source dist}
// Step 6: While Q is not empty
while(!pq.isEmpty()){
// // Step 7: Extract-Min from the queue
int[] cur = pq.poll();
int curNode = cur[0];
int curDist = cur[1];
// If the node is already visited, skip it
if (visited.contains(curNode)){
continue;
}
// Step 8: Add u to the visited set
visited.add(curNode);
// Step 9: For each adjacent vertex v in the adjacency list of u
if (graph.containsKey(curNode)){
for (int[] nei : graph.get(curNode)){
int nextNode = nei[0];
int nextWeight = nei[1];
// Step 10: Relax the edge (u, v)
if (curDist + nextWeight < dist[nextNode]){
dist[nextNode] = curDist + nextWeight;
pq.offer(new int[]{nextNode, dist[nextNode]});
}
}
}
}
return dist;
}
}
// TC: O((E+V)logV)
// SC: O(E+Vss)
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
import java.util.*;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
// Create a graph representation using a HashMap
Map<Integer, List<int[]>> edges = new HashMap<>();
for (int[] time : times) {
edges.computeIfAbsent(time[0], x -> new ArrayList<>()).add(new int[]{time[1], time[2]});
}
// Min-heap priority queue, to always expand the smallest distance node first
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
minHeap.offer(new int[]{0, k});
// Set to track visited nodes
Set<Integer> visited = new HashSet<>();
int t = 0;
// Dijkstra's algorithm main loop
while (!minHeap.isEmpty()) {
int[] current = minHeap.poll();
int w1 = current[0];
int n1 = current[1];
if (visited.contains(n1)) {
continue;
}
visited.add(n1);
t = Math.max(t, w1);
// Explore the neighbors of the current node
if (edges.containsKey(n1)) {
for (int[] neighbor : edges.get(n1)) {
int n2 = neighbor[0];
int w2 = neighbor[1];
if (!visited.contains(n2)) {
minHeap.offer(new int[]{w1 + w2, n2});
}
}
}
}
// Check if all nodes have been visited
return visited.size() == n ? t : -1;
}
}