题目描述
这是 LeetCode 上的 743. 网络延迟时间 ，难度为 中等。
Tag : 「最短路」、「图」、「优先队列（堆）」
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2 复制代码
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1 输出：1 复制代码
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2 输出：-1 复制代码
提示：
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- 所有 (ui, vi) 对都 互不相同（即，不含重复边）
基本分析
为了方便，我们约定 nn 为点数，mm 为边数。
根据题意，首先 nn 的数据范围只有 100100，mm 的数据范围为 60006000，使用「邻接表」或「邻接矩阵」来存图都可以。
同时求的是「从 kk 点出发，所有点都被访问到的最短时间」，将问题转换一下其实就是求「从 kk 点出发，到其他点 xx 的最短距离的最大值」。
Floyd（邻接矩阵）
根据「基本分析」，我们可以使用复杂度为 O(n^3)O(n3) 的「多源汇最短路」算法 Floyd 算法进行求解，同时使用「邻接矩阵」来进行存图。
此时计算量约为 10^6106，可以过。
跑一遍 Floyd，可以得到「从任意起点出发，到达任意起点的最短距离」。然后从所有 w[k][x]w[k][x] 中取 maxmax 即是「从 kk 点出发，到其他点 xx 的最短距离的最大值」。
代码：
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() { 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]); } } } } } 复制代码
- 时间复杂度：O(n^3)O(n3)
- 空间复杂度：O(n^2)O(n2)
朴素 Dijkstra（邻接矩阵）
同理，我们可以使用复杂度为 O(n^2)O(n2) 的「单源最短路」算法朴素 Dijkstra 算法进行求解，同时使用「邻接矩阵」来进行存图。
根据题意，kk 点作为源点，跑一遍 Dijkstra 我们可以得到从源点 kk 到其他点 xx 的最短距离，再从所有最短路中取 maxmax 即是「从 kk 点出发，到其他点 xx 的最短距离的最大值」。
朴素 Dijkstra 复杂度为 O(n^2)O(n2)，可以过。
代码：
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() { 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]); } } } } 复制代码
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(n^2)O(n2)
堆优化 Dijkstra（邻接表）
由于边数据范围不算大，我们还可以使用复杂度为 O(m\log{n})O(mlogn) 的堆优化 Dijkstra 算法进行求解。
堆优化 Dijkstra 算法与朴素 Dijkstra 都是「单源最短路」算法。
跑一遍堆优化 Dijkstra 算法求最短路，再从所有最短路中取 maxmax 即是「从 kk 点出发，到其他点 xx 的最短距离的最大值」。
此时算法复杂度为 O(m\log{n})O(mlogn)，可以过。
代码：
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() { 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 (int i = 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]}); } } } } } 复制代码
- 时间复杂度：O(m\log{n} + n)O(mlogn+n)
- 空间复杂度：O(m)O(m)
Bellman Ford（邻接表）
虽然题目规定了不存在「负权边」，但我们仍然可以使用可以在「负权图中求最短路」的 Bellman Ford 进行求解，该算法也是「单源最短路」算法，复杂度为 O(n * m)O(n∗m)。
代码：
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() { 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 (int i = he[a]; i != -1; i = ne[i]) { int b = e[i]; dist[b] = Math.min(dist[b], prev[a] + w[i]); } } } } } 复制代码
- 时间复杂度：O(n*m)O(n∗m)
- 空间复杂度：O(m)O(m)
SPFA（邻接表）
SPFA 是对 Bellman Ford 的优化实现，可以使用队列进行优化，也可以使用栈进行优化。
通常情况下复杂度为 O(k*m)O(k∗m)，kk 一般为 44 到 55，最坏情况下仍为 O(n * m)O(n∗m)，当数据为网格图时，复杂度会从 O(k*m)O(k∗m) 退化为 O(n*m)O(n∗m)。
代码：
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() { 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 (int i = 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; } } } } } 复制代码
- 时间复杂度：O(n*m)O(n∗m)
- 空间复杂度：O(m)O(m)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.743 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
