题目
有 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 <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- 所有
(ui, vi)对都 互不相同（即，不含重复边）
解题
前置知识
- 单源最短路径：指的是在加权图中，给定一个起点，求出它分别到其他顶点的**「最短路径」**。
- Dijkstra算法：
将所有节点分成两类：
- 已确定从起点到当前点的最短路长度的节点(「未确定节点」)。
- 未确定从起点到当前点的最短路长度的节点(「已确定节点」)。
每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离，直到所有点都被归类为「已确定节点」。
用节点 A「更新」节点 B 的意思是，用 起点到节点 A 的最短路长度 加上 从节点 A 到节点 B 的边的长度，去比较 起点到节点 B 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。
这里暗含的信息是：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。
可以这样理解，因为我们已经用了每一个「已确定节点」更新过了当前节点，无需再次更新（因为一个点不能多次到达）。而当前节点已经是所有「未确定节点」中与起点距离最短的点，不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。
方法一：Dijkstra算法 邻接矩阵
思路
本题求的是「从 k 点出发，所有点都被访问到的最短时间」，将问题转换一下其实就是求「从 k 点出发，到其他点 x 的最短距离的最大值」。
把表示路径无穷大的 INF 初始化为 。
代码中将节点编号减小了 ，从而使节点编号位于 范围，故下文中的 k 代表代码中的 k-1。
使用题目给出的数组 times 构建一个邻接矩阵(graph)，方便后面查找顶点关系与边权值。
因为边的权值有可能为 0（），所以应该把邻接矩阵中元素全部初始化为 INF 再开始构建邻接矩阵。
初始化表示最短距离的数组(dist)，其中 dist[i] 表示从节点 k 到节点 i 的最短路值。
初始化访问数组(visited)，其中 visited[i] 表示节点 i 是否被访问过。
循环 n 次：
- 每次找到「从k开始最短距离最小」且「未被访问过」的点
min。 - 标记
min顶点为已访问。 - 用顶点
min的「最小距离」更新其他顶点。
完成循环后遍历 dist 数组，从中取出「最短距离的最大值」(ans)，如果 ans==INF 说明不能使所有节点收到信号（从图的角度来说其实是该图的连通分量大于 1），返回 -1，否则直接返回 ans。
代码
朴素 Dijkstra 算法 + 邻接矩阵
class Solution {
private static final int INF = 100 * 6000;
public int networkDelayTime(int[][] times, int n, int k) {
// 邻接矩阵数组: graph[x][y]=weight 表示从x到y有权重为weight的边
int[][] graph = new int[n][n];
// 因为边的权值有可能为0, 初始化邻接矩阵为无穷大
for (int[] row : graph) Arrays.fill(row, INF);
// 构造邻接矩阵
for (int[] time : times) {
graph[time[0] - 1][time[1] - 1] = time[2];
}
// dist[i]=weight 表示从起点k到i的最短距离为weight
int[] dist = new int[n];
// 初始化所有顶点的“最短距离”为正无穷
Arrays.fill(dist, INF);
// 把起点相于自己的最短距离置为0
dist[k - 1] = 0;
// 初始化访问数组 visited[i]==true 表示顶点i已经被访问过 反之
boolean[] visited = new boolean[n];
// 迭代m次
for (int i = 0; i < n; i++) {
int min = -1;
// 找到「“最短距离”最小」且「未被访问过」的顶点 min
for (int j = 0; j < n; j++) {
if (visited[j]) continue;
if (min == -1 || dist[j] < dist[min]) min = j;
}
// 标记顶点 min 为已访问
visited[min] = true;
// 用顶点 min 的“最短距离”更新其他顶点
for (int j = 0; j < n; j++) {
dist[j] = Math.min(dist[j], dist[min] + graph[min][j]);
}
}
int ans = 0;
// 遍历“最短距离”数组 从中取出最大的
for (int d : dist) {
ans = Math.max(ans, d);
}
return ans == INF ? -1 : ans;
}
}
方法二：Bellman-Ford算法 动态规划 类存图
思路
既然是求单源最短路问题，也可以使用 Bellman-Ford 算法。
代码
class Solution {
private static final int INF = Integer.MAX_VALUE >> 1;
public int networkDelayTime(int[][] times, int n, int k) {
List<Edge> edges = new ArrayList<>();
for (int[] time : times) {
edges.add(new Edge(time[0] - 1, time[1] - 1, time[2]));
}
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, INF);
for (int i = 0; i < n; i++) dp[i][k - 1] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
for (Edge edge : edges) {
if (edge.dest == j) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][edge.src] + edge.weight);
}
}
}
}
int ans = 0;
for (int d : dp[n - 1]) {
ans = Math.max(ans, d);
}
return ans == INF ? -1 : ans;
}
static class Edge {
public int src;
public int dest;
public int weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
}
优化
仔细观察题目已经给了现成的图，只不过是用数组表示的：
times[e][0]表示e.srctimes[e][1]表示e.desttimes[e][2]表示e.weight
class Solution {
private static final int INF = Integer.MAX_VALUE >> 1;
public int networkDelayTime(int[][] times, int n, int k) {
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, INF);
for (int i = 0; i < n; i++) dp[i][k - 1] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int[] edge : times) {
if (edge[1] - 1 != j) continue;
dp[i][j] = Math.min(dp[i][j], dp[i - 1][edge[0] - 1] + edge[2]);
}
}
}
int ans = 0;
for (int d : dp[n - 1]) {
ans = Math.max(ans, d);
}
return ans == INF ? -1 : ans;
}
}
优化：滚动数组
因为动态规划中只需要用到当前行(dp[i])和上一行(dp[i-1])，所以可以使用滚动数组进行优化，具体来说：
只用维护一个 dist 数组表示「从起始顶点最多经过 条边到所有顶点的最短路」，每次循环拷贝一份 dist 为 prev 表示「从起始顶点最多经过 条边到所有顶点的最短路」。
class Solution {
private static final int INF = Integer.MAX_VALUE >> 1;
public int networkDelayTime(int[][] times, int n, int k) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[k - 1] = 0;
for (int i = 1; i < n; i++) {
int[] prev = dist.clone();
for (int dest = 0; dest < n; dest++) {
for (int[] edge : times) {
if (edge[1] - 1 != dest) continue;
dist[dest] = Math.min(dist[dest], dist[edge[0] - 1] + edge[2]);
}
}
}
int ans = 0;
for (int d : dist) {
ans = Math.max(ans, d);
}
return ans == INF ? -1 : ans;
}
}
优化：剪枝
如果在某次循环中没有最短路径被更新，就说明所有最短路径都被求出来了，接下来的可能路径也不会更短，就可以直接退出外循环。
class Solution {
private static final int INF = Integer.MAX_VALUE >> 1;
public int networkDelayTime(int[][] times, int n, int k) {
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[k - 1] = 0;
for (int i = 1; i < n; i++) {
boolean hasShorterPath = false;
int[] prev = dist.clone();
for (int[] edge : times) {
int src = edge[0] - 1;
int dest = edge[1] - 1;
int weight = edge[2];
if (dist[src] + weight < dist[dest]) {
dist[dest] = dist[src] + weight;
hasShorterPath = true;
}
}
if (!hasShorterPath) break;
}
int ans = 0;
for (int d : dist) {
ans = Math.max(ans, d);
}
return ans == INF ? -1 : ans;
}
}
评论区