Dijkstra迪杰斯特拉算法Java模板

package lanqiao;

import java.util.Arrays;

public class Dijkstra {
	public static void main(String[] args) {
		int n = 2021;
		int[][] map = new int[n + 1][n + 1]; // 二维矩阵存储各个点以及关系
		// 还有一种邻接表 使用动态的方式来存储 这样可以节省空间
		
		// 构造无向图 这里可以换成你需要的构建图方式
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n && j < i + 22; j++) {
				// 有向图的构造需要 动态添加比较好 或者仅更新一个节点 为0的节点就是不连通点，查找某一个点的其他连接点时需要判断 != 0
				map[i][j] = map[j][i] = lcm(i, j);
			}
		}
		
		// dijkstra算法 1-2021
		int[] dist = new int[n + 1]; // 由特殊路径得到的最短路径
		Arrays.fill(dist, Integer.MAX_VALUE); // 填充最大值 方便更新
		int[] pre = new int[n + 1]; // 前驱节点
		int[] s = new int[n + 1]; // 确定的点
		s[1] = 1;
		pre[1] = 0;
		dist[1] = 0;
		int cnt = 1;
		
		// 寻找当前点可以到达的下一个所有点 取其中最小的长度作为下一个确定最短路径的点
		// 从刚刚确定的那个点出发 寻找下一个到达的所有点 重复此过程 直到找到目标点
		int idx = 1; // idx就是当前点
		while (cnt != n) {
			int i = idx;
				// 开始找当前点下一个所有点 并更新 dist 以及 pre
				for (int j = 1; j <= n; j++) {
					// map[i][j] s[j] == 0 是找没有确定最短路径的点 map[i][j] != 0 是找连通的点 
					if (s[j] == 0 && map[i][j] != 0 && map[i][j] + dist[i] < dist[j]) {
						dist[j] = map[i][j] + dist[i];
						pre[j] = i;
					}
				}
				// 查找完毕 更新完毕 找当前dist中未确定最短距离即s中为0 并且 最短的距离的点，这个点就是下一个确认的最短距离的点
				int minDist = Integer.MAX_VALUE;
				for (int k = 1; k <= n; k++) {
					if (s[k] == 0) {
						if (dist[k] < minDist) {
							minDist = Math.min(idx, dist[k]);
							idx = k;
						}
					}
				}
				// idx就是下一个进入s的节点
				s[idx] = 1;
				cnt++;
		}
		
		System.out.println(dist[n]);
		
	}
	
	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
}

迪杰斯特拉算法总结：

构造图，可以使用二维矩阵，邻接表(Vector,ArrayList)。
如果不是连续的节点，可以把这些节点当作连续的，然后再构造的图中存储相应的Node节点或数据即可。使用三个数组。
**s[]**用来存放所有节点的下标，0表示未确定，1表示已经确定。
**dist[]**用来存放原点到某一个节点的路径长度，首先存放特殊路径，即从当前点到其下一个节点的距离，然后进行更新，得到最短距离。
**pre[]**用来存放当前下标对应节点的前驱节点的下标。有了它就可以输出整条路径了。