学习dijkstra算法
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
简介
Dijkstra算法 (迪杰斯特拉算法,卜老师纠正过是叫戴斯特比较标准)是典型最短路径算法,用于计算一个节点到其他节点的最短路径。
基本步骤:
- 指定起点s;
- 构建一个二维数组graph,用于存储节点之间的邻接关系,定义一个最短路径数组dist,记录起点s到达各个节点的最短路径,visited数组来标记已经求出最短路径的节点;
- 遍历每个节点,找出当前未被处理的最短路径节点x,然后访问其相邻节点y,判断s通过x到达y,比原本从起点s到达y的路径短,则更新s到达y的最短路径。反复循环判断,直到遍历完所有节点。
题目
743. 网络延迟时间
原题地址:https://leetcode.cn/problems/network-delay-time/description/
有 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)对都 互不相同(即,不含重复边)
题解
根据题目的要求,我们从节点 k 到达 节点x 的时间,就是其之间的最短路径。故我们可以默认节点 k 到达 其余节点的路径非常大(题目的数据无法计算的到的),然后我们去计算节点 k 到达 其它所有节点的最短路径。
其中,最大值如果不是我们默认设定的最大值,表示从 k 出发能访问到所有节点,则其中的最大值,即为访问所有节点所需要的时间。否则则说明存在k无法到达的节点。
过程如下:

下边用代码实现:
java
import java.util.Arrays;
/**
* 743. 网络延迟时间
* https://leetcode.cn/problems/network-delay-time/description/
*
* @author Salmon
* @since 2024-03-28
*/
public class M_743 {
public static void main(String[] args) {
// System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
// System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
// System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
// System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 1));
System.out.println(networkDelayTime(new int[][]{{1, 2, 1}, {2, 3, 7}, {1, 3, 4}, {2, 1, 2}}, 3, 2));
}
static int[][] graph; // 存储信号从源节点传递到目标节点的时间。
static boolean[] visited; // 标记当前信号是否已经访问过
static final int INF = 0x3f3f3f3f;
/**
* 计算多久才能使所有节点都收到信号
*
* @param times 表示信号经过 有向 边的传递时间
* times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。
* @param n n 个网络节点 标记为 1 到 n。
* @param k 出发点
* @return 多久能使所有节点收到信号,如果不能所有节点都收到,返回 -1
*/
private static int networkDelayTime(int[][] times, int n, int k) {
graph = new int[n][n];
for (int[] row : graph) {
Arrays.fill(row, INF);
}
for (int[] time : times) {
int ui = time[0];
int vi = time[1];
int wi = time[2];
graph[ui - 1][vi - 1] = wi;
}
return dijkstra(k, n);
}
/**
* 迪杰斯特拉
*
* @param k 出发节点
* @param n 节点个数
* @return 耗时
*/
private static int dijkstra(int k, int n) {
visited = new boolean[n]; // 标记当前节点是否访问过
int[] dist = new int[n]; // 节点k到达其他节点的最短路径
Arrays.fill(dist, INF);
dist[k - 1] = 0; // 节点k到达自己的最短距离为0
for (int i = 0; i < n; i++) {
int x = -1; // 记录找出的最短路径节点编号
int minD = INF; // 记录这个最短路径值
// 遍历所有节点,找出距离起点最小的节点
for (int j = 0; j < n; j++) {
// 当前节点没有被访问过,且路径比上一个节点小
if (!visited[j] && dist[j] < minD) {
x = j;
minD = dist[i];
}
}
// 说明不存在这个点,说明已经走完了
if (x == -1) {
break;
}
visited[x] = true; // 标记当前节点已经访问
// 遍历所有节点,更新通过当前的节点到达其它节点的最短路径
// 有些节点无法通过该节点访问到,则还是默认最大值
for (int j = 0; j < n; j++) {
// 如果当前找出的最短路径节点与当前遍历节点是连通的
if (graph[x][j] != INF) {
// 则看看从起点k到达该节点j的原本路径
// 与通过找出最短路径的节点x,来到达该节点j的路径
// 是否比原来的短,如果短则更新
int newDis = dist[x] + graph[x][j];
dist[j] = Math.min(dist[j], newDis);
}
}
}
int maxDis = Arrays.stream(dist).max().getAsInt();
// 如果还有k与某一节点的最短路径还是那个设定的最大值,说明k无法到达这一个节点
// 则返回-1
return maxDis == INF ? -1 : maxDis;
}
}

评论
0 条—
还没有评论,来说第一句