单源最短路径¶
dijkstra¶
dijkstra 算法可以在有权图(权值非负数)中求从起点到其他节点的最短路径算法。
需要注意两点:
dijkstra 算法可以同时求 起点到所有节点的最短路径
权值不能为负数
dijkstra 算法 和 我们之前讲解的prim算法思路非常接近,同样是贪心的思路,不断寻找距离 源点最近的没有访问过的节点。
重要
dijkstra三部曲:
第一步,选源点到哪个节点近且该节点未被访问过
第二步,该最近节点被标记访问过
第三步,更新非访问节点到源点的距离(即更新minDist数组)
minDist数组 用来记录 每一个节点距离源点的最小距离。
public int[] networkDelayTime(int[][] times, int n, int k) {
boolean[] visited = new boolean[n + 1];
int[] minDistance = new int[n + 1];
int[][] edges = new int[n + 1][n + 1];
Arrays.fill(minDistance, Integer.MAX_VALUE);
for (int[] edge : edges) {
Arrays.fill(edge, Integer.MAX_VALUE);
}
minDistance[k] = 0;
visited[k] = true;
for (int[] time : times) {
int from = time[0];
int to = time[1];
int value = time[2];
edges[from][to] = value;
}
for (int i = 1; i < n; i++) {
// select min k -> j
int minValue = Integer.MAX_VALUE;
int cur = k;
for (int j = 1; j <= n; j++) {
if (!visited[j] && minValue > minDistance[j]) {
minValue = minDistance[j];
cur = j;
}
}
visited[cur] = true;
for (int j = 1; j <= n; j++) {
if (!visited[j] && edges[cur][j] != Integer.MAX_VALUE && minDistance[j] > minDistance[cur] + edges[cur][j]) {
minDistance[j] = minDistance[cur] + edges[cur][j];
}
}
}
return minDistance;
}
dijkstra 的代码看上去和 prim 算法很像,其是思想都是一样的,区别在于 minDist[] 代表的含义不同,那么更新 minDist[] 的方式也就不同。
prim 算法是求最小生成树的,其中的 minDist[j] 代表
节点j
到目前已经求得的最小生成树的最小距离,也就是有新节点cur
加入后,minDist[j]=Math.min(minDist[j], grid[cur][j])
,grid[cur][j]
代表新加入的节点cur
到节点j
的距离dijkstra 算法是求单源最短距离,,其中的 minDist[v] 代表
节点v
到起点的最小距离,也就是有新节点cur
加入后,minDist[v]=Math.min(minDist[v], minDist[cur] + grid[cur][v])
,grid[cur][v]
代表新加入的节点cur
到节点v
的距离
// prim 更新 minDist[]
for (int j = 1; j <= v; j++) {
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
// dijkstra 更新 minDist[]
for (int v = 1; v <= n; v++) {
if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
minDist[v] = minDist[cur] + grid[cur][v];
}
}
dijkstra 堆优化版¶
import java.util.*;
class Edge {
int to; // 邻接顶点
int val; // 边的权重
Edge(int to, int val) {
this.to = to;
this.val = val;
}
}
class MyComparison implements Comparator<Pair<Integer, Integer>> {
@Override
public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {
return Integer.compare(lhs.second, rhs.second);
}
}
class Pair<U, V> {
public final U first;
public final V second;
public Pair(U first, V second) {
this.first = first;
this.second = second;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
List<List<Edge>> grid = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
grid.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt();
int p2 = scanner.nextInt();
int val = scanner.nextInt();
grid.get(p1).add(new Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点
// 存储从源点到每个节点的最短距离
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
// 记录顶点是否被访问过
boolean[] visited = new boolean[n + 1];
// 优先队列中存放 Pair<节点,源点到该节点的权值>
PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());
// 初始化队列,源点到源点的距离为0,所以初始为0
pq.add(new Pair<>(start, 0));
minDist[start] = 0; // 起始点到自身的距离为0
while (!pq.isEmpty()) {
// 1. 第一步,选源点到哪个节点近且该节点未被访问过(通过优先级队列来实现)
// <节点, 源点到该节点的距离>
Pair<Integer, Integer> cur = pq.poll();
if (visited[cur.first]) continue;
// 2. 第二步,该最近节点被标记访问过
visited[cur.first] = true;
// 3. 第三步,更新非访问节点到源点的距离(即更新minDist数组)
for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点,cur指向的节点为 edge
// cur指向的节点edge.to,这条边的权值为 edge.val
if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
minDist[edge.to] = minDist[cur.first] + edge.val;
pq.add(new Pair<>(edge.to, minDist[edge.to]));
}
}
}
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println(-1); // 不能到达终点
} else {
System.out.println(minDist[end]); // 到达终点最短路径
}
}
}