【Java版高级数据结构】最短路径(迪杰斯特拉算法)
本文代码: https://github.com/chenruoyu0319/data-structure-for-java/tree/main/%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84一、最短路径分析比如我们现在要对一个地图计算最短路径,首先我们要解决这个问题就要找准一个数据结构,很显然地图肯定是用图结构来表示最好了。具体:我们可以把每个路口看成一个点,路口之间的
一、最短路径分析
比如我们现在要对一个地图计算最短路径,首先我们要解决这个问题就要找准一个数据结构,很显然地图肯定是用图结构来表示最好了。
具体:我们可以把每个路口看成一个点,路口之间的路看作一条边。路的长度就是边的权重,即可得到以下这个图形:
这里我们就将地图转换成了我们熟悉的数据结构图,那么假设我要从1点作为起点,则就变成求1点到其他点的最短路径。
一般可以有三种解决思路:动态规划、DFS(深度优先遍历算法)、贪心算法,这里介绍用动态规划的思想来解决。
算法选择:经典算法之迪杰斯特拉(Dijkstra)算法,即单源最短路径算法,它是所有最短路径算法的基础,我们的地图软件最终使用的算法也是以他为基础进行的优化。所以弄懂它变得尤为重要。
二、迪杰斯特拉(Dijkstra)算法思路
核心思想分析:排序 + 贪心,
1.我们开一个dis数组,用来表示起始点到每个顶点的距离,最开始时我们赋值为无穷大。
2.加变量loc,初始赋值为起始点。
贪心的策略:在dis数组里面找离初始点最近的那个点
3.通过loc更新dis数组,因为加入一个点后我们就可以更新路径
4.在dis数组里面找离初始点最近的那个点,排除已经选择过的点,将之赋值给loc。
5.重复执行 3 4操作,直到所有点加完。
其中核心操作是第三步:我们应该如何来更新dis数组呢?
三、参考代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Djstl {
/**
6
8
1
1 3 10
1 5 50
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
*/
public static void main(String[] args) {
int n, m, x; // n表示点数,m表示边数,x表示我们起点
Map<Integer,String> routes = new HashMap<>();
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
m = cin.nextInt();
x = cin.nextInt();
int value[][] = new int[n + 1][n + 1]; // 表示点到点的邻接矩阵
int dis[] = new int[n + 1]; // 存最短路径的
for (int i = 1; i <= n; i++) {
dis[i] = Integer.MAX_VALUE;
for (int j = 1; j <= n; j++) {
// 初始化我们的地图
value[i][j] = -1; // 表示没有路的
if (i == j) {
value[i][j] = 0;
}
}
routes.put(i,"");
}
for (int i = 0; i < m; i++) { // 表示要输入m个边
int xx = cin.nextInt();
int yy = cin.nextInt();
int v = cin.nextInt(); // xx yy v表示从xx到yy有一条路 长度是v
value[xx][yy] = v;
// dis其实在第一个点时候可以在这里计算
if (xx == x) {
dis[yy] = v;
}
}
seach(x, dis, value, n,routes);
}
public static void seach(int x, int dis[], int value[][], int n,Map<Integer,String> routes) {
boolean mark[] = new boolean[n + 1];
mark[x] = true;
dis[x] = 0;
int count = 1;
routes.put(x,String.valueOf(x));
while (count <= n) { //O(n^2)
int loc = 0; // 表示新加的点
int min = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++) { // 求dis里面的最小值 优先队列,堆 logn
if (!mark[i] && dis[i] < min) {
min = dis[i];
loc = i;
}
}
if (loc == 0) {
break; // 表示没有可以加的点了
}
// 初始化第一个新加进来的节点
if (routes.get(loc) == ""){
routes.put(loc,"1->" + loc);
}
mark[loc] = true;
//只需要关注 我们加进来的点 能有哪些路径就可以了,不用扫描所有的dis 最好的情况应该可以达到o(nlogn),最坏的情况才是O(n^2)
for (int i = 1; i <= n; i++) {
if (value[loc][i] != -1 && (dis[loc] + value[loc][i] < dis[i])) {
dis[i] = dis[loc] + value[loc][i];
routes.put(i,routes.get(loc) + "->" + i);
}
}
count++;
}
for (int i = 1; i <= n; i++) {
System.out.println(x + "到 " + i + "的最短路径为 :" + dis[i]);
}
for (int i = 1; i <= n; i++) {
System.out.println(x + "到 " + i + "的最短路径为 :" + routes.get(i));
}
}
}
dis[i]);
}
for (int i = 1; i <= n; i++) {
System.out.println(x + "到 " + i + “的最短路径为 :” + routes.get(i));
}
}
}
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)