LeetCode之团灭Dijkstra算法

目录

算法背景

算法描述

算法模版

力扣刷题

参考文章

算法背景

地图中的导航功能就是基于迪杰斯特拉算法(Dijkstra)实现的,力扣周赛中经常出现基于这个算法的变种题

算法描述

算法目标：给出一个起始点，我们可以求出到达其他所有点的最短路径

• 例：假设v​1​​为源点，找从v​1​​到其它节点的最短路径

• 集合S用来存储已经找到的最短路径
• v1到自己显然最短，故为初始最短路径

初始表格

第一轮：从v1出发，计算v1到其它节点的距离（无法连接则用“无穷”符号）

计算v1到其它节点的距离，无法连接则用“无穷”符号

• 全表找最小值，发现v1到v6最短为3
• S中添加一条最短路径：v1——v6
• v6列标红不再考虑

v1——v6为新发现的最短路径

第二轮：从v1——v6出发，计算v1通过v6到其它节点的距离

• 已知v1到v6为3；v6可以到v2,v4,v5；因此，v1通过v6到其它节点的距离为3+n，n为6到各节点的距离

v1——v6到其它现存节点的距离（v6列已删除）

• 在全表中找最小值（v6列已经删除），此时4为最小值，对应路径v1——v6——v5
• 添加最短路径v1——v6——v5
• v5列不再考虑

v1——v6——v5为新发现的最短路径

第三轮：从v1——v6——v5出发，计算v1通过v6及v5到其它节点的距离

• 已知v1——v6——v5长度为4；
• 发现，v5不能到现存的其它任何一个节点，因此距离全部为“无穷”

v1——v6——v5到其它现存节点的距离（v5，v6列已删除）

• 看全表（v5和v6已经删除）找最小值，5是最小值，对应的路径是v1——v6——v2
• 添加最短路径v1——v6——v2
• v2列不再考虑

新最短路径：v1——v6——v2

第四轮：从v1——v6——v2出发，计算v1通过v6及v2到其它节点的距离

v1——v6——v2到其它现存节点的距离（v2，v5，v6已删除）

• 遍历全表（v2，v5和v6已经删除）发现，9最小，对应的路径为v1——v6——v4
• 添加最短路径v1——v6——v4
• v4列不再考虑

新最短路径：v1——v6——v4

第五轮：从v1——v6——v4出发，计算v1通过v6及v4到其它节点的距离

计算v1——v6——v4到其它节点的距离（只剩v3列）

• 遍历全表发现，12是现存的最小值，对应v1——v6——v2——v3路径最短
• 添加最短路径v1——v6——v2——v3
• v3列不再考虑

添加最后一条最短路径：v1——v6——v2——v3

• 由于全部列已经删除，因此结束遍历

• 最终的表格

最终表格

• 每列的标红值，则为v1到该节点的最短距离；从S列中找结尾为该列的路径。
• 例如，v2列标红值为5，说明v1到v2的最短路径为5
• S中结尾为v2，对应的路径为v1——v6——v2

结果汇总

• v1到各节点的路径及其最短距离
  • v6：v1——v6 = 3
  • v5：v1——v6——v5 = 4
  • v4：v1——v6——v4 = 9
  • v3：v1——v6——v2——v3 = 12
  • v2：v1——v6——v2 = 5

算法模版

public class Dijkstra {
	
	static class Node {
		int x; // 节点编号
		int lenth;// 用于记录起点到该节点的最短路径的临时变量

		public Node(int x, int lenth) {
			this.x = x;
			this.lenth = lenth;
		}
	}

	public static void main(String[] args) {

		int[][] map = new int[6][6];// 记录权值，顺便记录链接情况，可以考虑附加邻接表
		initmap(map);// 初始化
		boolean visited[] = new boolean[6];// 判断是否已经确定
		int len[] = new int[6];// 用于记录起点到对应节点的最终的最短路径长度
		for (int i = 0; i < 6; i++) {
			len[i] = Integer.MAX_VALUE;
		}
 
		
		PriorityQueue<Node> q1 = new PriorityQueue<>((a, b) -> {
			return a.lenth - b.lenth;
		});
		
		len[0] = 0;// 从0这个点开始
		q1.add(new Node(0, 0));


		while (!q1.isEmpty()) {
			Node t1 = q1.poll();
			int index = t1.x;// 节点编号
			int length = t1.lenth;// 节点当前点距离
			visited[index] = true;// 抛出的点确定
			for (int i = 0; i < map[index].length; i++) {
				if (map[index][i] > 0 && !visited[i]) {
					Node node = new Node(i, length + map[index][i]);
					if (len[i] > node.lenth)// 需要更新节点的时候更新节点并加入队列
					{
						len[i] = node.lenth;
						q1.add(node);
					}
				}
			}
		}
		for (int i = 0; i < 6; i++) {
			System.out.println(len[i]);
		}
	}

	static Comparator<Node> com = new Comparator<Node>() {

		public int compare(Node o1, Node o2) {
			return o1.lenth - o2.lenth;
		}
	};

	private static void initmap(int[][] map) {
		map[0][1] = 2;
		map[0][2] = 3;
		map[0][3] = 6;
		map[1][0] = 2;
		map[1][4] = 4;
		map[1][5] = 6;
		map[2][0] = 3;
		map[2][3] = 2;
		map[3][0] = 6;
		map[3][2] = 2;
		map[3][4] = 1;
		map[3][5] = 3;
		map[4][1] = 4;
		map[4][3] = 1;
		map[5][1] = 6;
		map[5][3] = 3;
	}
}

力扣刷题

public class LeetCode1976到达目的地的方案数 {

	public int countPaths(int n, int[][] roads) {

		boolean visited[] = new boolean[n];// 判断是否已经确定
		int len[] = new int[n]; // 记录从起点到各节点的最短路径长度
		int[] cnt = new int[n]; // 记录从起点到各节点的最短路径数量

		for (int i = 0; i < n; i++) {
			len[i] = Integer.MAX_VALUE;
		}

		int[][] map = initmap(roads, n);

		PriorityQueue<Node> q1 = new PriorityQueue<>((a, b) -> {
			return a.lenth - b.lenth;
		});

		len[0] = 0;// 从0这个点开始
		q1.add(new Node(0, 0));
		cnt[0] = 1; // start -> start的最短路径只有一条

		while (!q1.isEmpty()) {
			Node t1 = q1.poll();
			int index = t1.x;// 节点编号
			int length = t1.lenth;// 节点当前点距离
			visited[index] = true;// 抛出的点确定
			for (int i = 0; i < map[index].length; i++) {
				if (map[index][i] > 0 && !visited[i]) {
					Node node = new Node(i, length + map[index][i]);
					if (len[i] > node.lenth)// 需要更新节点的时候更新节点并加入队列
					{
						cnt[i] = cnt[index];
						len[i] = node.lenth;
						q1.add(node);
					} else if (len[i] == node.lenth) {
						// 如果当前最短路径长度相等，则累加路径数量
						// 如果发现有另一个路径，它的长度和当前的最短路径长度相等，那么这条路径也是最短路径之一。
						// 因此，我们需要将这条路径的数量加到当前节点的最短路径数量 cnt[i] 中
						cnt[i] = (cnt[i] + cnt[index]) % 1000000007;
					}
				}
			}
		}
		return cnt[n - 1];

	}

	private int[][] initmap(int[][] roads, int n) {

		int[][] map = new int[n][n];

		for (int i = 0; i < roads.length; i++) {
			map[roads[i][0]][roads[i][1]] = roads[i][2];
			map[roads[i][1]][roads[i][0]] = roads[i][2];
		}

		return map;

	}

	class Node {
		int x; // 节点编号
		int lenth;// 用于记录起点到该节点的最短路径的临时变量

		public Node(int x, int lenth) {
			this.x = x;
			this.lenth = lenth;
		}
	}

	public static void main(String[] args) {

		int[][] roads = { { 1, 0, 10 } };
		new LeetCode1976到达目的地的方案数().countPaths(2, roads);
	}
}

public class LeetCode2642设计可以求最短路径的图类 {

	class Graph {

		int[][] map = null;
		boolean visited[] = null;
		int len[] = null;

		public Graph(int n, int[][] edges) {

			map = new int[n][n];
			visited = new boolean[n];// 判断是否已经确定
			len = new int[n]; // 记录从起点到各节点的最短路径长度

			for (int i = 0; i < edges.length; i++) {
				map[edges[i][0]][edges[i][1]] = edges[i][2];
			}
			for (int i = 0; i < n; i++) {
				len[i] = Integer.MAX_VALUE;
			}
		}

		public void addEdge(int[] edge) {

			dijkstra(edge[0]);
			map[edge[0]][edge[1]] = edge[2];

		}

		public int shortestPath(int node1, int node2) {
			// 先检查 node1 到 node2 之间是否有直接的边
	        if (map[node1][node2] > 0) {
	        	return map[node1][node2]; 
	        }
 
			return len[node2];

		}
		
	    public void dijkstra(int source) {
	    	
	        Arrays.fill(visited, false);
	        Arrays.fill(len, Integer.MAX_VALUE);
	    	
			PriorityQueue<Node> q1 = new PriorityQueue<>((a, b) -> {
				return a.lenth - b.lenth;
			});

			len[source] = -1;// 从node1这个点开始
			q1.add(new Node(source, 0));

			while (!q1.isEmpty()) {

				Node t1 = q1.poll();
				int index = t1.x;// 节点编号
				int length = t1.lenth;// 节点当前点距离
				visited[index] = true;// 抛出的点确定
				for (int i = 0; i < map[index].length; i++) {
					if (map[index][i] > 0 && !visited[i]) {
						Node node = new Node(i, length + map[index][i]);
						if (len[i] > node.lenth)// 需要更新节点的时候更新节点并加入队列
						{
							len[i] = node.lenth;
							q1.add(node);
						}
					}
				}
			}
	    	
	    }

		class Node {
			int x; // 节点编号
			int lenth;// 用于记录起点到该节点的最短路径的临时变量

			public Node(int x, int lenth) {
				this.x = x;
				this.lenth = lenth;
			}
		}
	}

}

public class LeetCode2662前往目标的最小代价{

	public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
		// 创建一个优先级队列，用于存储每个位置和到达该位置的代价，按代价从小到大排序
		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
			return a[2] - b[2];
		});
		// 初始化结果为从起点到终点的直线距离
		int res = dist(start, target);
		// 将起点加入优先级队列
		pq.offer(new int[] { start[0], start[1], 0 });
		// 创建一个 HashMap 用于存储已访问过的位置和到达该位置的最小代价
		Map<String, Integer> vis = new HashMap<>();
		vis.put(getKey(start), 0);

		while (!pq.isEmpty()) {
			// 每次从队列中取出代价最小的位置
			int[] p = pq.poll();
			// 遍历所有特殊路径
			for (int[] sp : specialRoads) {
				int[] p1 = new int[] { sp[0], sp[1] };
				int[] p2 = new int[] { sp[2], sp[3] };
				// 计算从当前位置到特殊路径起点的代价，再加上特殊路径的代价
				int d = p[2] + dist(p, p1) + sp[4];
				String key = getKey(p2);
				// 获取之前到达特殊路径终点的最小代价，如果没有则为从起点到终点的直线距离
				int x = vis.getOrDefault(key, dist(start, p2));
				// 如果新的代价小于之前的最小代价，更新最小代价
				if (d < x) {
					vis.put(key, d);
					pq.offer(new int[] { p2[0], p2[1], d });
					// 更新结果，当前位置到特殊路径终点的代价加上从特殊路径终点到目标位置的代价
					res = Math.min(res, d + dist(p2, target));
				}
			}
		}
		return res;
	}

	// 计算两点之间的代价
	private int dist(int[] p1, int[] p2) {
		return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
	}

	// 将位置转换为字符串，用于在 HashMap 中作为键
	private String getKey(int[] p) {
		return p[0] + "_" + p[1];
	}
}

参考文章

【看完必懂】Dijkstra算法（附案例详解） - 知乎

https://www.cnblogs.com/bigsai/p/11537975.html文章来源地址https://www.toymoban.com/news/detail-476625.html

到了这里，关于LeetCode之团灭Dijkstra算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！