Dijkstra 算法

参考 https://zhuanlan.zhihu.com/p/129373740

Djstra 算法：每次从「未求出最短路径的点」中取出距离起点 最小路径的点，以这个点为桥梁刷新「未求出最短路径的点」的距离

# Dijkstra 算法图解方式一

# 图解（外部剪枝）

如下所示，用优先队列演示图

此处剪枝是在 for 外部剪枝

只有当前路径 dis > minDis 时候才剪枝，若 dis == minDis 不应该剪枝

例如：[u, v, 二者距离]

[1, 2, 1]，[1, 3, 2]

首先优先队列中含有 [2, 1]，[3, 2]；并更新 minDis [2] = 1, minDis [3] = 2

若下一次弹出 [2, 1]

若轮播图加载不出来，请刷新

	import java.util.*;

	class Solution {
	public static void main(String[] args) {
	System.out.println(new Solution().spfa(7, new int[][]{
	{0, 1, 18},
	{0, 4, 23},
	{0, 5, 4},
	{0, 6, 6},
	{1, 2, 5},
	{1, 3, 8},
	{1, 4, 12},
	{2, 3, 10},
	{3, 4, 15},
	{3, 5, 20},
	{4, 5, 25},
	{5, 6, 7},
	},4));
	}

	int INF = (int) 1e6;

	// dijkstra
	public int spfa(int n, int[][] edges, int t) {
	// 不可达就是 INF
	List<int[]>[] graph = new List[n];
	for (int i = 0; i < n; i++) {
	graph[i] = new ArrayList<>();
	}
	for (int[] edge : edges) {
	graph[edge[0]].add(new int[]{edge[1], edge[2]});
	graph[edge[1]].add(new int[]{edge[0], edge[2]});
	}
	//0 -> i 的最小权重
	int[] dis = new int[n];
	Arrays.fill(dis, INF);
	dis[0] = 0;
	// 每次取出最短的，[v, w]
	PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
	minHeap.add(new int[]{0, 0});
	while (!minHeap.isEmpty()) {
	// 每次从可达路径中取出满足条件的最小值
	int[] minNode = minHeap.poll();
	int u = minNode[0];
	int w = minNode[1];
	// 大于了当前最小权重，就不需要压入
	// 只有大于才需要
	if (w > dis[u]) {
	continue;
	}
	if (u == t - 1) {
	return w;
	}
	// 选出下一个可达的路径，u -> i
	for (int[] v : graph[u]) {
	int nextW = w + v[1];
	// 让 0 到达当前 v 的权重最小
	dis[v[0]] = Math.min(dis[v[0]], nextW);
	// 选择新的 nextW
	minHeap.add(new int[]{v[0], nextW});
	}
	}
	return -1;
	}
	}

若轮播图加载不出来，请刷新

	import java.util.*;

	class Solution {
	public static void main(String[] args) {
	System.out.println(new Solution().spfa(6, new int[][]{
	{0, 1, 10},
	{0, 2, 3},
	{1, 5, 7},
	{1, 4, 5},
	{2, 3, 1},
	{2, 4, 6},
	{3, 4, 6},
	{4, 5, 2}
	}));
	}

	int INF = (int) 1e6;

	// dijkstra
	public int spfa(int n, int[][] edges) {
	// 不可达就是 INF
	List<int[]>[] graph = new List[n];
	for (int i = 0; i < n; i++) {
	graph[i] = new ArrayList<>();
	}
	for (int[] edge : edges) {
	graph[edge[0]].add(new int[]{edge[1], edge[2]});
	graph[edge[1]].add(new int[]{edge[0], edge[2]});
	}
	//0 -> i 的最小权重
	int[] dis = new int[n];
	Arrays.fill(dis, INF);
	dis[0] = 0;
	// 每次取出最短的，[v, w]
	PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
	minHeap.add(new int[]{0, 0});
	while (!minHeap.isEmpty()) {
	// 每次从可达路径中取出满足条件的最小值
	int[] minNode = minHeap.poll();
	int u = minNode[0];
	int w = minNode[1];
	if (u == n - 1) {
	return w;
	}
	// 选出下一个可达的路径，u -> i
	for (int[] v : graph[u]) {
	int nextW = w + v[1];
	// 大于等于了当前最小权重，就不需要压入
	if (nextW >= dis[v[0]]) {
	continue;
	}
	// 可能只有一个小于
	// 让 0 到达当前 v 的权重最小
	dis[v[0]] = Math.min(dis[v[0]], nextW);
	// 选择新的 nextW
	minHeap.add(new int[]{v[0], nextW});
	}
	}
	return -1;
	}
	}