题目描述

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

示例：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

算法

(dijkstra) $时间复杂是 O(n^2+m), n 表示点数，m 表示边数$

问至少需要多少时间才能从K到达任何一个结点。这实际上是一个有向图求单源最短路径的问题，求出K点到每一个点到最短路径，然后取其中最大的一个就是需要的时间了。而且没有负权边，所以可以使用Dijkstra，Bellman-Ford，spfa。本次先写一个Dijkstra，下次更新其他2个。

Java 代码

class Solution {
    int N = 109;
    int[][] g = new int[N][N];      // g[][]存储图的邻接矩阵, dist[]表示每个点到起点的距离
    int[] dist = new int[N];        // 存储k号点到每个点的最短距离
    boolean st[] = new boolean[N];  // 存储每个点的最短距离是否已确定

    // 问至少需要多少时间才能从K到达任何一个结点。这实际上是一个有向图求最短路径的问题，求出K点到每一个点到最短路径，然后取其中最大的一个就是需要的时间了。
    public int networkDelayTime(int[][] times, int n, int k) {
        if (times.length == 0 || times[0].length == 0) {
            return -1;
        }

        // 初始化领接矩阵
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == j) {
                    g[i][j] = 0;
                } else {
                    g[i][j] = 0x3f3f3f;
                }
            }
        }

        // 遍历times填充邻接表
        for (int[] t : times) {
            int a = t[0];
            int b = t[1];
            int c = t[2];
            g[a][b] = c;
        }

        return dijkstra(n, k);
    }

    private int dijkstra(int n, int k) {
        // 填充dist距离数组
        Arrays.fill(dist, 0x3f3f3f);
        // 第K个点到自身的距离为0
        dist[k] = 0;

        // 有N个点所以要进行N次 迭代
        for (int i = 1; i <= n; i++) {
            // 当前没有访问的点
            int t = -1;

            // 不在s集合，并且距离起点最小的点,如果没有更新过，则进行更新,发现更短的路径, 则进行更新
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }

            //加入到s集合中
            st[t] = true;
            //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }

        // 如果k点到达不了n号节点，如题目要求:如果不能使所有节点收到信号，返回-1
        // dist[i]为0x3f3f3f，说明k点和当前i点不联通
        int res = -1;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);
        }
        return res >= 0x3f3f3f ? -1 : res;
    }
}

算法2

(Bellman-Ford)

套用BellMan-Form算法模版，效率不如dijkstra。

Java 代码

class Solution {
    class Edge {
        int a, b, w;
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    int[] dist;         // 存储k号点到每个点的最短距离
    boolean[] st;       // 存储每个点的最短距离是否已确定
    int[] bk;           // 备份数组
    Edge[] edges;
    int m = 0;          // 边数

    // 问至少需要多少时间才能从K到达任何一个结点。这实际上是一个有向图求最短路径的问题，求出K点到每一个点到最短路径，然后取其中最大的一个就是需要的时间了。
    public int networkDelayTime(int[][] times, int n, int k) {
        if (times.length == 0 || times[0].length == 0) {
            return -1;
        }

        dist = new int[n + 1];
        st = new boolean[n + 1];
        m = times.length;
        edges = new Edge[m + 1];

        // 初始化边
        for (int i = 0; i < m; i++) {
            int a = times[i][0];
            int b = times[i][1];
            int w = times[i][2];

            edges[i] = new Edge(a, b, w);
        }

        return bellmanFord(n, k);
    }

    // 求k到n的最短路距离，如果无法从1走到n，则返回-1。
    private int bellmanFord(int n, int k) {
        Arrays.fill(dist, 0x3f3f3f);
        dist[k] = 0;

        for (int i = 1; i <= n; i++) {
            bk = Arrays.copyOf(dist, n + 1);
            for (int j = 0; j < m; j++) {
                int a = edges[j].a;
                int b = edges[j].b;
                int w = edges[j].w;
                //   w
                // a -> b
                dist[b] = Math.min(dist[b], bk[a] + w);
            }
        }

        int res = -1;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);
        }
        return res >= 0x3f3f3f / 2 ? -1 : res; 
    }
}

算法3

(spfa)

spfa基本上是最快的，比dijkstra和bellmanFord都快

Java 代码

class Solution {
    int idx = 0;
    int[] h;
    int[] e;
    int[] w ;
    int[] next;
    int[] dist;
    boolean[] st;
    Queue<Integer> q;

    public int networkDelayTime(int[][] times, int n, int k) {
        if (times.length == 0 || times[0].length == 0) {
            return 0;
        }
        q = new ArrayDeque<>(n);
        h = new int[n + 1];
        e = new int[times.length + 1];
        w = new int[times.length + 1];
        next = new int[times.length + 1];
        dist = new int[n + 1];
        st = new boolean[n + 1];
        Arrays.fill(h, -1);

        for (int i = 0; i < times.length; i++) {
            int a = times[i][0];
            int b = times[i][1];
            int c = times[i][2];
            add(a, b, c);
        }

        return spfa(n, k);
    }

    private int spfa(int n, int k) {
        Arrays.fill(dist, 0x3f3f3f);
        dist[k] = 0;
        st[k] = true;
        //声明一个队列保存更新过的节点
        Queue<Integer> q = new ArrayDeque<>(n);
        q.add(k);

        while (!q.isEmpty()) {
            // t是可能更小距离的点
            Integer t = q.poll();
            st[t] = false;

            // 更新可以更新的点
            for (int i = h[t]; i != -1; i = next[i]) {
                int j = e[i];
                //如果当前节点可以被更新，就做更新操作，并将该节点加入到队列中
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }

        int res = -1;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);
        }
        return res >= 0x3f3f3f ? -1 : res;
    }

    private void add(int a, int b, int c) {
        e[idx] = b;
        next[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }
}