Topic describes

This is 743 on LeetCode. Network latency, medium difficulty.

Tag: “shortest”, “graph”, “priority queue (heap)”

There are n network nodes, labeled 1 through N.

I’ll give you a list times, which is how long it takes for a signal to pass through a 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, we send a signal from some node K. How long will it take for all nodes to receive signals? If all nodes cannot receive signals, -1 is returned.

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 = 1Copy the code

Example 3:

Input: times = [1,2,1]], n = 2, k = 2Copy 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) pairs are different (i.e., without repeating edges)

Fundamental analysis

For convenience, we agree that NNN is the number of points and MMM is the number of edges.

First of all, the data range of NNN is only 100100100, while that of MMM is 600060006000. It can be saved by “adjacency list” or “adjacency matrix”.

At the same time is “starting from KKK point, all points are visited to the shortest time”, the problem is converted to “starting from KKK point, to other points XXX shortest distance maximum”.

Floyd (Adjacency matrix)

According to the “basic analysis”, we can use the complexity of O(N3)O(N ^3)O(N3)O “multi-source convergence shortest circuit” algorithm Floyd algorithm to solve, and use the “adjacency matrix” to save the graph.

At this time, the calculation amount is about 10610^6106, which can be passed.

Run Floyd to get “the shortest distance from any starting point to any starting point”. Then from all w[k][x]w[k][x]w[k][x] w[k][x] maxMaxmax is “from KKK point, to other point XXX shortest maximum distance”.

Code:

class Solution {
    int N = 110, M = 6010;
    int[][] w = new int[N][N];
    int INF = 0x3f3f3f3f;
    int n, k;
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = w[j][i] = i == j ? 0: INF; }}for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            w[u][v] = c;
        }
        floyd();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, w[k][i]);
        }
        return ans >= INF / 2 ? -1 : ans;
    }
    void floyd(a) {
        for (int p = 1; p <= n; p++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
                }
            }
        }
    }
}
Copy the code
  • Time complexity: O(n3)O(n^3)O(n3)
  • Space complexity: O(n2)O(n^2)O(n2)

Naive Dijkstra (Adjacency matrix)

Similarly, we can use the simple Dijkstra algorithm of O(n2)O(n^2)O(n2) to solve the problem, and use the “adjacency matrix” to save the graph.

KKK point as the source point, run through Dijkstra we can get the shortest distance from the source point KKK to other points XXX, and then take maxmaxmax from all the shortest is “starting from KKK point, to other points XXX maximum shortest distance”.

The naive Dijkstra is O(n2)O(n^2)O(n2).

Code:

class Solution {
    int N = 110, M = 6010;
    int[][] w = new int[N][N];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, k;
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = w[j][i] = i == j ? 0: INF; }}for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            w[u][v] = c;
        }
        dijkstra();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    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
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

Heap optimization Dijkstra

Since the range of edge data is not large, we can also use heap optimization Dijkstra algorithm with complexity O(mlog⁡n)O(m\log{n})O(mlogn) to solve the problem.

Heap optimization Dijkstra algorithm and naive Dijkstra are “single source shortest” algorithm.

Run through the heap optimization Dijkstra algorithm to find the shortest circuit, and then take maxMaxmax from all the shortest circuit, which is “the maximum distance from KKK point to other points XXX”.

In this case, the algorithm complexity is O(mlog⁡n)O(m\log{n})O(mlogn), which can pass.

Code:

class Solution {
    int N = 110, M = 6010;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];
    int n, k, idx;
    int INF = 0x3f3f3f3f;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        Arrays.fill(he, -1);
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        dijkstra();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void dijkstra(a) {
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        dist[k] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{k, 0});
        while(! q.isEmpty()) {int[] poll = q.poll();
            int id = poll[0], step = poll[1];
            if (vis[id]) continue;
            vis[id] = true;
            for (inti = he[id]; i ! = -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[id] + w[i]) {
                    dist[j] = dist[id] + w[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }
}
Copy the code
  • O(mlog⁡n+n)O(m\log{n} +n)O(mlogn+n)
  • Space complexity: O(m)O(m)O(m)

Bellman Ford (Adjacency List)

Although the title states that there is no “negative weight edge”, we can still use Bellman Ford, which can find the shortest circuit in “negative weight graph”, and this algorithm is also the “single-source shortest circuit” algorithm with complexity O(n∗m)O(n * m)O(n∗m).

Code:

class Solution {
    int N = 110, M = 6010;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, m, k, idx;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        m = ts.length;
        Arrays.fill(he, -1);
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        bf();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void bf(a) {
        Arrays.fill(dist, INF);
        dist[k] = 0;
        for (int p = 1; p <= m; p++) {
            int[] prev = dist.clone();
            for (int a = 1; a <= n; a++) {
                for (inti = he[a]; i ! = -1; i = ne[i]) {
                    int b = e[i];
                    dist[b] = Math.min(dist[b], prev[a] + w[i]);
                }
            }
        }
    }
}
Copy the code
  • Time complexity: O(n∗m)O(n*m)O(n∗m)
  • Space complexity: O(m)O(m)O(m)

SPFA (Adjacency List)

SPFA is an optimized implementation of Bellman Ford that can be optimized using either queues or stacks.

In general, the complexity is O(k∗m)O(K *m)O(K ∗m), and KKK is generally 444 to 555. In the worst case, it is still O(n∗m)O(N *m)O(n∗m). When the data is a grid graph, The complexity degrades from O(k∗m)O(K *m)O(K ∗m) to O(n∗m)O(N *m)O(n∗m).

Code:

class Solution {
    int N = 110, M = 6010;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    int[] dist = new int[N];
    boolean[] vis = new boolean[N];
    int INF = 0x3f3f3f3f;
    int n, k, idx;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        w[idx] = c;
        idx++;
    }
    public int networkDelayTime(int[][] ts, int _n, int _k) {
        n = _n; k = _k;
        Arrays.fill(he, -1);
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            add(u, v, c);
        }
        spfa();
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }
    void spfa(a) {
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        dist[k] = 0;
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(k);
        vis[k] = true;
        while(! d.isEmpty()) {int poll = d.pollFirst();
            vis[poll] = false;
            for (inti = he[poll]; i ! = -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[poll] + w[i]) {
                    dist[j] = dist[poll] + w[i];
                    if (vis[j]) continue;
                    d.addLast(j);
                    vis[j] = true;
                }
            }
        }
    }
}
Copy the code
  • Time complexity: O(n∗m)O(n*m)O(n∗m)
  • Space complexity: O(m)O(m)O(m)

The last

This is the No.743 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.