折800网站程序,做网站营销发布文章,ui设计模板网站,手机网站html有 n 个网络节点#xff0c;标记为 1 到 n。
给你一个列表 times#xff0c;表示信号经过 有向 边的传递时间。 times[i] (ui, vi, wi)#xff0c;其中 ui 是源节点#xff0c;vi 是目标节点#xff0c; wi 是一个信号从源节点传递到目标节点的时间。
现在#xff0c;…有 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算法流程 初始化 邻接矩阵 g 存储边权。 dis 数组存储源点到各点的最短距离初始为 INF。 done 数组标记节点是否已确定最短路径。 Dijkstra 主循环 选择当前未处理的、距离最短的节点 x。 如果 x 不可达返回 -1。 更新 maxDis 为 dis[x]因为 dis[x] 是递增的。 标记 x 为已处理。 松弛 x 的所有邻居 y更新 dis[y]。 终止条件 所有节点已处理返回 maxDis最长延迟时间。
时间复杂度 邻接矩阵实现O(n^2)适用于稠密图。 堆优化优先队列O(E log V)适用于稀疏图但本题未使用。
空间复杂度 O(n^2)邻接矩阵存储。
1. 初始化
final int INF Integer.MAX_VALUE / 2; // 防止加法溢出
int[][] g new int[n][n]; // 邻接矩阵
for (int[] row : g) {Arrays.fill(row, INF);
} INF表示“无穷大”用于初始化不可达的边。Integer.MAX_VALUE / 2 是为了防止后续计算 dis[x] g[x][y] 时溢出。 g邻接矩阵g[i][j] 表示从节点 i 到 j 的传输时间权重。 初始化邻接矩阵所有边初始为 INF表示初始时所有节点之间不可达。 2. 构建图的邻接矩阵
for (int[] t : times) {g[t[0] - 1][t[1] - 1] t[2];
} times 是一个二维数组其中 times[i] [u, v, w] 表示从节点 u 到 v 的传输时间为 w。 存储到邻接矩阵 g[t[0] - 1][t[1] - 1] t[2]因为节点编号从 1 开始而数组索引从 0 开始所以需要 -1 调整。 3. Dijkstra 算法初始化
int maxDis 0;
int[] dis new int[n];
Arrays.fill(dis, INF);
dis[k - 1] 0;
boolean[] done new boolean[n]; maxDis记录所有最短路径中的最大值即网络延迟时间。 disdis[i] 表示从源节点 k 到节点 i 的最短距离初始为 INF不可达。 dis[k - 1] 0源节点到自身的距离为 0。 done标记节点是否已经确定最短路径。 4. Dijkstra 主循环
while (true) {int x -1;for (int i 0; i n; i) {if (!done[i] (x 0 || dis[i] dis[x])) {x i;}}if (x 0) {return maxDis; // 所有节点已处理完毕}if (dis[x] INF) { // 有节点无法到达return -1;}maxDis dis[x]; // 更新最大延迟时间done[x] true; // 标记 x 的最短路径已确定for (int y 0; y n; y) {dis[y] Math.min(dis[y], dis[x] g[x][y]);}
}
(1) 选择当前未处理的最短路径节点
int x -1;
for (int i 0; i n; i) {if (!done[i] (x 0 || dis[i] dis[x])) {x i;}
} x当前未处理!done[i]且距离 dis[i] 最小的节点。 贪心策略每次选择距离源节点最近的未处理节点进行扩展。
(2) 检查是否所有节点已处理
if (x 0) {return maxDis; // 所有节点已处理完毕
} x 0表示所有节点都已处理返回 maxDis即最长延迟时间。
(3) 检查是否有节点不可达
if (dis[x] INF) { // 有节点无法到达return -1;
} dis[x] INF表示当前节点 x 无法从源节点到达直接返回 -1。
(4) 更新 maxDis 并标记 x 为已处理
maxDis dis[x]; // 更新最大延迟时间
done[x] true; // 标记 x 的最短路径已确定 maxDis由于 Dijkstra 每次处理的 dis[x] 是递增的所以直接更新即可。 done[x] true表示 x 的最短路径已确定后续不再更新。
(5) 松弛操作更新邻居的最短距离
for (int y 0; y n; y) {dis[y] Math.min(dis[y], dis[x] g[x][y]);
} 松弛Relaxation尝试通过 x 缩短 y 的最短路径 如果 dis[x] g[x][y] dis[y]则更新 dis[y]。
完整版代码
class Solution {public int networkDelayTime(int[][] times, int n, int k) {final int INF Integer.MAX_VALUE / 2; // 防止加法溢出int[][] g new int[n][n]; // 邻接矩阵for (int[] row : g) {Arrays.fill(row, INF);}for (int[] t : times) {g[t[0] - 1][t[1] - 1] t[2];}int maxDis 0;int[] dis new int[n];Arrays.fill(dis, INF);dis[k - 1] 0;boolean[] done new boolean[n];while (true) {int x -1;for (int i 0; i n; i) {if (!done[i] (x 0 || dis[i] dis[x])) {x i;}}if (x 0) {return maxDis; // 最后一次算出的最短路就是最大的}if (dis[x] INF) { // 有节点无法到达return -1;}maxDis dis[x]; // 求出的最短路会越来越大done[x] true; // 最短路长度已确定无法变得更小for (int y 0; y n; y) {// 更新 x 的邻居的最短路dis[y] Math.min(dis[y], dis[x] g[x][y]);}}}
}示例
输入
times [[2,1,1],[2,3,1],[3,4,1]], n 4, k 2
执行流程 初始化 dis [INF, 0, INF, INF]源节点 k2 的距离为 0。 第一次循环 选择 x1dis[1] 0。 松弛邻居 y0 和 y2 dis[0] min(INF, 0 1) 1 dis[2] min(INF, 0 1) 1 maxDis 0。 第二次循环 选择 x0 或 x2dis[0] 1, dis[2] 1。 假设选 x0但没有邻居可更新。 maxDis 1。 第三次循环 选择 x2。 松弛邻居 y3 dis[3] min(INF, 1 1) 2 maxDis 1。 第四次循环 选择 x3。 没有邻居可更新。 maxDis 2。 结束 所有节点已处理返回 maxDis 2。
最终输出2最长延迟时间。
