目录
- 题目描述：
- Dijkstra 算法 (朴素版)：
- 用Dijkstra解决本题：
题目描述：
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。 小蓝的图由2021 个结点组成，依次编号1 至2021。
对于两个不同的结点a, b，如果a 和b 的差的绝对值大于21，则两个结点之间没有边相连； 如果a 和b
的差的绝对值小于等于21，则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连。 例如：结点1 和结点23 之间没有边相连；结点3
和结点24 之间有一条无向边，长度为24； 结点15 和结点25 之间有一条无向边，长度为75。 请计算，结点1 和结点2021
之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题
答案：10266837
Dijkstra 算法 (朴素版)：
迪杰斯特拉（dijkstra）算法是单源最短路径问题的求解方法。单源最短路径就在给出一个固定网络，指定一个原点s，一个目标点e，求这两个点之间的最短路径。
迪杰斯特拉算法是，基于贪心算法，目标是求最短路径，既然整个路径是最短得，那么分支也应该是最短的，所以按我的理解，迪杰斯特拉算法，就是在找最短子路径，然后迭代下去，这样每个子路径是最优的，那么整个路径就是最优的
需要的数组有一维数组dist，dist[i]记录的是i点到起点的距离，edges二维数组edges[i][j]表示点i到点j的距离。最后是visit一维数组visit[i]表示每个点是否被遍历过
如果对这个算法一点不了解的话可以看这个大哥讲的是真不错：迪杰斯特拉算法详讲。
这里直接给出dijkstra的模板代码：
import java.util.*;
public class Main {
public static int edges[][];//存放所有边edges[i][j]代表从i ~ j 的距离
public static int dist[];//存入起点到所有点的距离。
public static boolean visit[];//标记当前点是否被遍历过
public static int INF = 0x3f3f3f3f;
public static void main(String[] args) {
}
public static int dijkstra(int n) {//传入终点
for(int i = 1; i <= n; i ++) {
int index = -1;//未被访问的点，到原点最短距离的点。
dist[1] = 0;//原点到原点的距离为0
for(int j = 1; j <= n; j ++) {//找最小点
if(!visit[j] &&(index == -1 || dist[j] < dist[index])) {
index = j;
}
}
visit[index] = true;//标记用过
for(int j = 1; j <= n; j ++) {//更新
if(dist[index] + edges[index][j] < dist[j]) {
dist[j] = dist[index] + edges[index][j];
}
}
}
if(dist[n] == INF) return - 1;
return dist[n];
}
}
这里要注意的是迪杰斯特拉算法，边的权值不能为负，真是一条边为负都不行：
以下图为例：
代码：
import java.util.*;
public class Main {
public static int edges[][];//存放所有边edges[i][j]代表从i ~ j 的距离
public static int dist[];//存入起点到所有点的距离。
public static boolean visit[];//标记当前点是否被遍历过
public static int INF = 0x3f3f3f3f;
public static void main(String[] args) {
edges = new int[5][5];
dist = new int[5];
visit = new boolean[5];
Arrays.fill(dist, INF);
for(int i = 1; i <= 4; i ++)
for(int j = 1; j <= 4; j ++) edges[i][j] = INF;
edges[1][1] = 0;
edges[2][2] = 0;
edges[3][3] = 0;
edges[4][4] = 0;
edges[1][2] = 1;
edges[1][3] = 2;
edges[1][4] = 8;
edges[2][4] = 4;
edges[3][4] = 5;
edges[3][2] = -2;
System.out.println(dijkstra(4));
// for(int i = 1; i <= 4; i ++) System.out.print(dist[i] + " ");
}
public static int dijkstra(int n) {//传入终点
for(int i = 1; i <= n; i ++) {
int index = -1;//未被访问的点，到原点最短距离的点。
dist[1] = 0;//原点到原点的距离为0
for(int j = 1; j <= n; j ++) {//找最小点
if(!visit[j] &&(index == -1 || dist[j] < dist[index])) {
index = j;
}
}
visit[index] = true;
for(int j = 1; j <= n; j ++) {
if(dist[index] + edges[index][j] < dist[j]) {
dist[j] = dist[index] + edges[index][j];
}
}
}
if(dist[n] == INF) return - 1;
return dist[n];
}
}
输出：
正确答案是 4，这是迪杰斯特拉算法特性导致的，最开始点2到原点距离最短，会选择点2进行更新，但不会选择点3。
后续即使用点3更新了点2，由于点2已经被使用过了，所以无法再使用了。
本算法和floyd算法本质不同是floyd算法记录了任意两点的最优距离，本算法是记录任意一点到起点的最优距离。（Floyd算法可以允许路径有负权，但回路不能为负。）
用Dijkstra解决本题：
了解dijkstra后，代码就非常好写了，这里直接给出本题代码。
代码：
import java.util.Arrays;
public class text {
public static int edges[][];//存放所有边edges[i][j]代表从i ~ j 的距离
public static int dist[];//存入起点到所有点的距离。
public static boolean visit[];//标记当前点是否被遍历过
public static int INF = 0x3f3f3f3f;
public static void main(String[] args) {
// TODO Auto-generated method stub
int n = 2022;
edges = new int[n][n];
dist = new int[n];
visit = new boolean[n];
for(int i = 1; i <= 2021; i ++)
for(int j = 1; j <= 2021; j ++) {
if(Math.abs(i - j) <= 21) {
edges[i][j] = getgb(i, j);
}
else
edges[i][j] = INF;
}
Arrays.fill(dist, INF);
System.out.print(dijkstra(2021));
}
public static int getgb(int x, int y) {//最小公因数
int maxgy = 1;
int minone = Math.min(x, y);
for(int i = 1; i <= minone; i ++)
if(x % i == 0 && y % i == 0)
maxgy = i;
return x * y / maxgy;
}
public static int dijkstra(int n) {
for(int i = 1; i <= n; i ++) {
int index = -1;
dist[1] = 0;//初始化
for(int j = 1; j <= n; j ++) {//找距离原点最近的点
if(!visit[j] && (index == -1 || dist[j] < dist[index])) {
index = j;
}
}
visit[index] = true;//标记用过
for(int j = 1; j <= n; j ++) {//更新
if(dist[index] + edges[index][j] < dist[j]) {
dist[j] = dist[index] + edges[index][j];
}
}
}
if(dist[n] == INF) return - 1;
return dist[n];
}
}
