Algorithm
Problem Name: 743. Network Delay Time
Problem Link: https://leetcode.com/problems/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:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1 Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2 Output: -1
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.)
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
Map();
for (int[] time : times) {
map.computeIfAbsent(time[0], j -> new ArrayList<>()).add(new TimeNode(time[1], time[2]));
}
PriorityQueue < TimeNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));
pq.add(new TimeNode(k, 0));
int maxTime = 0;
Set < Integer> visited = new HashSet<>();
visited.add(k);
while (!pq.isEmpty() && visited.size() < n) {
TimeNode removed = pq.remove();
visited.add(removed.node);
maxTime = Math.max(maxTime, removed.time);
for (TimeNode conn : map.getOrDefault(removed.node, new ArrayList < >())) {
if (visited.contains(conn.node)) {
continue;
}
pq.add(new TimeNode(conn.node, removed.time + conn.time));
}
}
return visited.size() == n ? maxTime : -1;
}
class TimeNode {
int node;
int time;
public TimeNode(int node, int time) {
this.node = node;
this.time = time;
}
}
}
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const networkDelayTime = function(times, n, k) {
const graph = {}
for(const [u, v, w] of times) {
if(graph[u] == null) graph[u] = []
graph[u][v] = w
}
const visited = new Array(n + 1).fill(false)
const pq = new PQ((a, b) => a[0] < b[0])
pq.push([0, k])
let res = 0
while(!pq.isEmpty()) {
const [dist, cur] = pq.pop()
if(visited[cur]) continue
visited[cur] = true
n--
res = dist
if(graph[cur]) {
for(const nxt of Object.keys(graph[cur])) {
pq.push([res + graph[cur][nxt], nxt])
}
}
}
return n === 0 ? res : -1
};
class PQ {
constructor(comparator = (a, b> => a > b) {
this.heap = []
this.top = 0
this.comparator = comparator
}
size() {
return this.heap.length
}
isEmpty() {
return this.size() === 0
}
peek() {
return this.heap[this.top]
}
push(...values) {
values.forEach((value) => {
this.heap.push(value)
this.siftUp()
})
return this.size()
}
pop() {
const poppedValue = this.peek()
const bottom = this.size() - 1
if (bottom > this.top) {
this.swap(this.top, bottom)
}
this.heap.pop()
this.siftDown()
return poppedValue
}
replace(value) {
const replacedValue = this.peek()
this.heap[this.top] = value
this.siftDown()
return replacedValue
}
parent = (i) => ((i + 1) >>> 1) - 1
left = (i) => (i << 1) + 1
right = (i) => (i + 1) << 1
greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
siftUp = () => {
let node = this.size() - 1
while (node > this.top && this.greater(node, this.parent(node))) {
this.swap(node, this.parent(node))
node = this.parent(node)
}
}
siftDown = () => {
let node = this.top
while (
(this.left(node) < this.size() && this.greater(this.left(node), node)) ||
(this.right(node) < this.size() && this.greater(this.right(node), node))
) {
let maxChild =
this.right(node) < this.size() &&
this.greater(this.right(node), this.left(node))
? this.right(node)
: this.left(node)
this.swap(node, maxChild)
node = maxChild
}
}
}
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def networkDelayTime(self, times, N, K):
q, t, adj = [(0, K)], {}, collections.defaultdict(list)
for u, v, w in times:
adj[u].append((v, w))
while q:
time, node = heapq.heappop(q)
if node not in t:
t[node] = time
for v, w in adj[node]:
heapq.heappush(q, (time + w, v))
return max(t.values()) if len(t) == N else -1
Input
times = [[1,2,1]], n = 2, k = 1
Output
1
#4 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0743_NetworkDelayTime
{
public int NetworkDelayTime(int[][] times, int N, int K)
{
var graph = new Dictionary < int, List());
graph[edge[0]].Add(new Node(edge[2], edge[1]));
}
var pq = new MinPriorityQueue();
pq.Insert(new Node(0, K));
var distances = new Dictionary < int, int>();
while (pq.Size() > 0)
{
var node = pq.DeleteMin();
if (distances.ContainsKey(node.Target)) continue;
distances.Add(node.Target, node.Distance);
if (graph.ContainsKey(node.Target))
foreach (var edge in graph[node.Target])
if (!distances.ContainsKey(edge.Target))
pq.Insert(new Node(node.Distance + edge.Distance, edge.Target));
}
if (distances.Count != N) return -1;
return distances.Values.Max();
}
public class Node : IComparable < Node>
{
public Node(int distance, int target)
{
Distance = distance;
Target = target;
}
public int Distance { get; set; }
public int Target { get; set; }
public int CompareTo(Node other)
{
return Distance.CompareTo(other.Distance);
}
}
public class MinPriorityQueue : PriorityQueue
{
public MinPriorityQueue() : base() { }
public MinPriorityQueue(int initCapacity) : base(initCapacity) { }
protected override void Sink(int k)
{
while (2 * k < = N)
{
int j = 2 * k;
if (j < N && pq[j].CompareTo(pq[j + 1]) > 0) j++;
if (pq[k].CompareTo(pq[j]) < = 0) break;
Swap(k, j);
k = j;
}
}
protected override void Swim(int k)
{
while (k > 1 && pq[k / 2].CompareTo(pq[k]) > 0)
{
Swap(k / 2, k);
k = k / 2;
}
}
public Node Min() => First();
public Node DeleteMin() => Delete();
}
public abstract class PriorityQueue
{
protected int N;
protected Node[] pq;
public PriorityQueue() : this(1) { }
public PriorityQueue(int initCapacity)
{
this.N = 0;
pq = new Node[initCapacity + 1];
}
public bool IsEmpty() => N == 0;
public int Size() => N;
public Node First()
{
if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
return pq[1];
}
public void Insert(Node x)
{
if (N >= pq.Length - 1)
Resize(pq.Length * 2);
pq[++N] = x;
Swim(N);
}
protected abstract void Swim(int k);
public Node Delete()
{
var result = pq[1];
Swap(1, N--);
Sink(1);
pq[N + 1] = null;
if (N > 0 && N == (pq.Length - 1) / 4)
Resize(pq.Length / 2);
return result;
}
protected abstract void Sink(int k);
private void Resize(int newCapacity)
{
var temp = new Node[newCapacity + 1];
for (int i = 1; i < = N; i++)
temp[i] = pq[i];
pq = temp;
}
protected void Swap(int index1, int index2)
{
var temp = pq[index1];
pq[index1] = pq[index2];
pq[index2] = temp;
}
}
}
}
Input
times = [[1,2,1]], n = 2, k = 1
Output
1