# 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
Tag:
The back-end
algorithm
# Leetcode daily Question Series -743- Network latency time

## [Blog link]

## [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 node`K`

Send 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 all**Each other is not the same**(that is, without repeating edges)

Related Topics

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

## [Topic link]

## [making address]

## [思路介绍]

### 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++**

- Add when no node exists
- The initial null
- Initialize the first edge a-b- NULL
- Add new node a-b'-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
) {
add(time[0],time[1], time[2]);
}
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]);
priorityQueue.add(new int[]{k,0});
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