# Leetcode's Question of the Day series - Network latency | more challenging in August

Posted on Dec. 3, 2022, 10:17 a.m. by 郝淑華
Category: The back-end

# Leetcode daily Question Series -743- Network latency time

The way to study ?

## [Topic description]

There are n network nodes, labeled 1 through N.

I give you a list times, which is how long it takes the signal to pass the directed edge. Times [I] = (UI, vi, wi), where UI is the source node, vi is the target node, and WI is the time when a signal is transmitted from the source node to the target node.

Now, from some nodeKSend out a signal. How long does it take for all nodes to receive the signal? If the signal cannot be received by all nodes, return- 1 。 Example 1:

Input: times = [,1,1 [2], [2,3,1], [3,4,1]], n = 4, k = 2 output: 2Copy the code

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1 Output: 1Copy the code

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2 Output: -1Copy the code

Tip:

• 1 = k = n = 100
• 1 = times.length = 6000
• times[i].length == 3
• 1 = ui, vi = n
• ui ! = vi
• 0 = wi = 100
• all(ui, vi)For allEach other is not the same(that is, without repeating edges)

Related Topics

• Depth-first search
• figure
• The short circuit
• Heap (priority queue)
• ? ? 0 301

## [思路介绍]

### Idea 1: Violence + DFS +hash

• Depth traversal of all edges and length from node K
• None of the edges are repeated
• The TLE
• Simple DFS are too easy to search space explosion
MapInteger, Integer map = new HashMap();

public int networkDelayTime(int[][] times, int n, int k) {
map.put(k, 0);
Arrays.sort(times, (a, b) - {
if (a[0] == b[0]) {
if (a[1] == b[1]) {
return a[2] - b[2];
} else {
return a[1] - b[1]; }}return a[0] - b[0];
});
dfs(times, k,0);
if(map.size() ! = n) {return -1;
}
int max = 0;
for (int key : map.keySet()
) {
max = Math.max(max, map.get(key));
}
return max;
}

public void dfs(int[][] times, int k, int index) {
for (int i = index; i  times.length; i++) {
if (times[i][0] == k) {
// The current element has a shorter path
if (map.containsKey(times[i][1])) {
map.put(times[i][1], Math.min(map.get(k) + times[i][2], map.get(times[i][1))); }else {
map.put(times[i][1], map.get(k) + times[i][2]);
}
dfs(times, times[i][1], index + 1); }}}Copy the code

Time complexity O( $n^{3}$

### Floyd algorithm + graph

• Initialize the digraph to a maximum of 100 nodes with each node value greater than 6000
• Let's say we have a maximum of 110 nodes, a maximum of 6010 edges,
• Initialize the value of each edge
• Calculate the shortest path from each point to the rest points by Floyd function
• Return the shortest path from k to the rest of the points
int N = 110, m = 6010;
int[][] w = new int[N][N];
int INF = 0x3f3f3f3f;
int n, k;

public int networkDelayTime(int[][] times, int _n, int _k) {
n = _n;
k = _k;
for (int i = 0; i  N; i++) {
for (int j = 0; j  N; j++) {
w[i][j] = w[j][i] = i == j ? 0: INF; }}for (int[] time : times
) {
w[time[0]][time[1]] = time[2];
}
floyd();
int ans = 0;
for (int i = 1; i = n; i++) {
ans = Math.max(ans, w[k][i]);
}
return ans = INF ? -1 : ans;
}

public void floyd(a) {
// I represents all node relationships, as long as I can find the path from j-l to participate in the comparison
for (int i = 1; i = n; i++) {
for (int j = 1; j = n; j++) {
for (int l = 1; l = n; l++) { w[j][l] = Math.min(w[j][l], w[j][i] + w[i][l]); }}}}Copy the code

Time complexity $O(n^{3})$

### Idea 3: Naive Dijkstra (adjacencies list)

• Three leaf big guy know really much, real name system envy
• Optimized part of Floyd algorithm, but the overall time complexity does not change
• Initialize the access array and record the access status
• The idea behind this algorithm is
• Two types of nodes are defined, one is undetermined node, the other is determined node
• Undetermined node: The shortest distance from the starting point K to the current node is not determined
• Identified node: The shortest distance from the starting point K to the current node has been determined
• 1. Iterate over all nodes
• 2. Each time an undetermined node pops up, it is classified as a determined node
• Pop-up condition:
• The current node has not been scanned
• The distance value from the starting point to the current node is shorter than previously calculated | | The first unscanned node (satisfies only one)

Updates the undetermined minimum through the determined minimum

int N = 110, m = 6010;
int[][] w = new int[N][N];
int INF = 0x3f3f3f3f;
int n, k;
int[] dist = new int[N];
boolean[] vis = new boolean[N];

public int networkDelayTime(int[][] times, int _n, int _k) {
n = _n;
k = _k;
for (int i = 0; i  N; i++) {
for (int j = 0; j  N; j++) {
w[i][j] = w[j][i] = i == j ? 0: INF; }}for (int[] time : times
) {
w[time[0]][time[1]] = time[2];
}
int ans = 0;
dijkstra();
for (int i = 1; i = n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans = INF ? -1 : ans;
}

public void dijkstra(a) {
Arrays.fill(vis, false);
Arrays.fill(dist, INF);
dist[k] = 0;
for (int p = 1; p = n; p++) {
int t = -1;
for (int i = 1; i = n; i++) {
if(! vis[i]  (t == -1 || dist[i]  dist[t])) t = i;
}
vis[t] = true;
for (int i = 1; i = n; i++) { dist[i] = Math.min(dist[i], dist[t] + w[t][i]); }}}Copy the code

Time complexity $O(n^{2})$

### Idea four: heap optimization Dijkstra + linked list build diagram

• First of all through the chain building (two days ago encountered) head insertion method to build
• He is the head node of the set of edges corresponding to a node, e is the node to which the current edge points, ne is the next edge of the current node, and w is time consuming
• Dist represents the shortest path from the starting point to each node, and index represents the number of edges
• So the add function represents that
• Add when no node exists
• A new edge relationship points to node B e[index] = b
• The next edge ne of the current node refers to the next edge corresponding to h[a] (not exist when initialized =-1).
• Assign the first associated edge index to the current header node h[a] and associate it to e[index]
• index++
• When there is a node
• A new edge relationship points to node B e[index] = b
• Next edge index ne[index] = next edge relationship h[a]
• The first edge associated with the current head node h[a] is converted to the latest edge index index
• index++
• The initial null
• Initialize the first edge a-b- NULL
int N = 110,M = 6010;
boolean[] vis = new boolean[N];
int[] he = new int[N],e = new int[M],ne = new int[M],w = new int[M], dist = new int[N];
int INF = 0x3f3f3f3f;
int n,k, index;
void add(int a, int b , int c){
e[index] = b;
ne[index] = he[a];
he[a] = index;
w[index] = c;
index++;
}
public int networkDelayTime(int[][] times, int _n, int _k) {
n = _n; k = _k;
Arrays.fill(he,-1);
for (int[] time: times
) {
}
dijkstra();
int ans = 0;
for (int i = 1; i = n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans  INF / 2 ? -1 : ans;
}
private void dijkstra(a){
Arrays.fill(vis,false);
Arrays.fill(dist,INF);
dist[k] = 0;
PriorityQueueint[] priorityQueue = new PriorityQueue((a,b)-a[1]-b[1]);
while(! priorityQueue.isEmpty()){int[] temp = priorityQueue.poll();
int node = temp[0];
if (vis[node]){
continue;
}
for (inti = he[node]; i ! = -1; i= ne[i]) {
int j = e[i];
if (dist[j]  dist[node]+w[i]){
dist[j] = dist[node]+w[i];
priorityQueue.add(new int[]{j,dist[j]}); }}}}Copy the code

O(m*log{n} +n) O(mlogn+n)

The rest of the three leaves I don't understand. They're too hard to read

Search