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 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
  • 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 code

Time complexity O(
n 3 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 ) 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 ) 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
  • 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 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