Leetcode daily Question Series -743- Network latency time
[Blog link]
The way to study 🐔
The nuggets home page
[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 codeExample 2:
Input: times = [[1,2,1]], n = 2, k = 1 Output: 1Copy the codeExample 3:
Input: times = [[1,2,1]], n = 2, k = 2 Output: -1Copy the codeTip:
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui ! = vi0 <= wi <= 100- all
(ui, vi)For allEach 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]
Leetcode title link
[making address]
Code link
[思路介绍]
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
Map<Integer, 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 codeTime complexity O(
)
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 codeTime complexity
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 codeTime complexity
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;
PriorityQueue<int[]> 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 codeO(m*log{n} +n) O(mlogn+n)
The rest of the three leaves I don’t understand. They’re too hard to read