Dijkstra 算法代码步骤[leetcode.743网络延迟时间]

有 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

算法流程

1. 初始化：

   • 邻接矩阵 g 存储边权。

   • dis 数组存储源点到各点的最短距离，初始为 INF。

   • done 数组标记节点是否已确定最短路径。

2. Dijkstra 主循环：

   • 选择当前未处理的、距离最短的节点 x。

   • 如果 x 不可达，返回 -1。

   • 更新 maxDis 为 dis[x]（因为 dis[x] 是递增的）。

   • 标记 x 为已处理。

   • 松弛 x 的所有邻居 y，更新 dis[y]。

3. 终止条件：

   • 所有节点已处理，返回 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：记录所有最短路径中的最大值（即网络延迟时间）。

• dis：dis[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

执行流程：

1. 初始化：

   • dis = [INF, 0, INF, INF]（源节点 k=2 的距离为 0）。

2. 第一次循环：

   • 选择 x=1（dis[1] = 0）。

   • 松弛邻居 y=0 和 y=2：

     • dis[0] = min(INF, 0 + 1) = 1

     • dis[2] = min(INF, 0 + 1) = 1

   • maxDis = 0。

3. 第二次循环：

   • 选择 x=0 或 x=2（dis[0] = 1, dis[2] = 1）。

   • 假设选 x=0，但没有邻居可更新。

   • maxDis = 1。

4. 第三次循环：

   • 选择 x=2。

   • 松弛邻居 y=3：

     • dis[3] = min(INF, 1 + 1) = 2

   • maxDis = 1。

5. 第四次循环：

   • 选择 x=3。

   • 没有邻居可更新。

   • maxDis = 2。

6. 结束：

   • 所有节点已处理，返回 maxDis = 2。

最终输出：2（最长延迟时间）。