Java实现Dijkstra输出最短路径的实例
作者:lqh 发布时间:2023-09-01 17:44:02
标签:Java,Dijkstra
Java实现Dijkstra输出指定起点到终点的最短路径
前言:
最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径。
马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现。
而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出。
package graph.dijsktra;
import graph.model.Point;
import java.util.*;
/**
* Created by MHX on 2017/9/13.
*/
public class Dijkstra {
private int[][] map; // 地图结构保存
private int[][] edges; // 邻接矩阵
private int[] prev; // 前驱节点标号
private boolean[] s; // S集合中存放到起点已经算出最短路径的点
private int[] dist; // dist[i]表示起点到第i个节点的最短路径
private int pointNum; // 点的个数
private Map<Integer, Point> indexPointMap; // 标号和点的对应关系
private Map<Point, Integer> pointIndexMap; // 点和标号的对应关系
private int v0; // 起点标号
private Point startPoint; // 起点
private Point endPoint; // 终点
private Map<Point, Point> pointPointMap; // 保存点和权重的映射关系
private List<Point> allPoints; // 保存所有点
private int maxX; // x坐标的最大值
private int maxY; // y坐标的最大值
public Dijkstra(int map[][], Point startPoint, Point endPoint) {
this.maxX = map.length;
this.maxY = map[0].length;
this.pointNum = maxX * maxY;
this.map = map;
this.startPoint = startPoint;
this.endPoint = endPoint;
init();
dijkstra();
}
/**
* 打印指定起点到终点的最短路径
*/
public void printShortestPath() {
printDijkstra(pointIndexMap.get(endPoint));
}
/**
* 初始化dijkstra
*/
private void init() {
// 初始化所有变量
edges = new int[pointNum][pointNum];
prev = new int[pointNum];
s = new boolean[pointNum];
dist = new int[pointNum];
indexPointMap = new HashMap<>();
pointIndexMap = new HashMap<>();
pointPointMap = new HashMap<>();
allPoints = new ArrayList<>();
// 将map二维数组中的所有点转换成自己的结构
int count = 0;
for (int x = 0; x < maxX; ++x) {
for (int y = 0; y < maxY; ++y) {
indexPointMap.put(count, new Point(x, y));
pointIndexMap.put(new Point(x, y), count);
count++;
allPoints.add(new Point(x, y));
pointPointMap.put(new Point(x, y), new Point(x, y, map[x][y]));
}
}
// 初始化邻接矩阵
for (int i = 0; i < pointNum; ++i) {
for (int j = 0; j < pointNum; ++j) {
if (i == j) {
edges[i][j] = 0;
} else {
edges[i][j] = 9999;
}
}
}
// 根据map上的权重初始化edges,当然这种算法是没有单独加起点的权重的
for (Point point : allPoints) {
for (Point aroundPoint : getAroundPoints(point)) {
edges[pointIndexMap.get(point)][pointIndexMap.get(aroundPoint)] = aroundPoint.getValue();
}
}
v0 = pointIndexMap.get(startPoint);
for (int i = 0; i < pointNum; ++i) {
dist[i] = edges[v0][i];
if (dist[i] == 9999) {
// 如果从0点(起点)到i点最短路径是9999,即不可达
// 则i节点的前驱节点不存在
prev[i] = -1;
} else {
// 初始化i节点的前驱节点为起点,因为这个时候有最短路径的都是与起点直接相连的点
prev[i] = v0;
}
}
dist[v0] = 0;
s[v0] = true;
}
/**
* dijkstra核心算法
*/
private void dijkstra() {
for (int i = 1; i < pointNum; ++i) { // 此时有pointNum - 1个点在U集合中,需要循环pointNum - 1次
int minDist = 9999;
int u = v0;
for (int j = 1; j < pointNum; ++j) { // 在U集合中,找到到起点最短距离的点
if (!s[j] && dist[j] < minDist) { // 不在S集合,就是在U集合
u = j;
minDist = dist[j];
}
}
s[u] = true; // 将这个点放入S集合
for (int j = 1; j < pointNum; ++j) { // 以当前刚从U集合放入S集合的点u为基础,循环其可以到达的点
if (!s[j] && edges[u][j] < 9999) {
if (dist[u] + edges[u][j] < dist[j]) {
dist[j] = dist[u] + edges[u][j];
prev[j] = u;
}
}
}
}
}
private void printDijkstra(int endPointIndex) {
if (endPointIndex == v0) {
System.out.print(indexPointMap.get(v0) + ",");
return;
}
printDijkstra(prev[endPointIndex]);
System.out.print(indexPointMap.get(endPointIndex) + ",");
}
private List<Point> getAroundPoints(Point point) {
List<Point> aroundPoints = new ArrayList<>();
int x = point.getX();
int y = point.getY();
aroundPoints.add(pointPointMap.get(new Point(x - 1, y)));
aroundPoints.add(pointPointMap.get(new Point(x, y + 1)));
aroundPoints.add(pointPointMap.get(new Point(x + 1, y)));
aroundPoints.add(pointPointMap.get(new Point(x, y - 1)));
aroundPoints.removeAll(Collections.singleton(null)); // 剔除不在地图范围内的null点
return aroundPoints;
}
public static void main(String[] args) {
int map[][] = {
{1, 2, 2, 2, 2, 2, 2},
{1, 0, 2, 2, 0, 2, 2},
{1, 2, 0, 2, 0, 2, 2},
{1, 2, 2, 0, 2, 0, 2},
{1, 2, 2, 2, 2, 2, 2},
{1, 1, 1, 1, 1, 1, 1}
}; // 每个点都代表权重,没有方向限制
Point startPoint = new Point(0, 3); // 起点
Point endPoint = new Point(5, 6); // 终点
Dijkstra dijkstra = new Dijkstra(map, startPoint, endPoint);
dijkstra.printShortestPath();
}
}
package graph.model;
public class Point {
private int x;
private int y;
private int value;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public Point(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
@Override
public String toString() {
return "{" +
"x=" + x +
", y=" + y +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
if (x != point.x) return false;
return y == point.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
}
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望通过本文能帮助到大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/u012712087/article/details/77995721
0
投稿
猜你喜欢
- 一、TkMybatisTkmybatis 是基于 Mybatis 框架开发的一个工具,通过调用它提供的方法实现对单表的数据操作,不需要写任何
- java 避免出现NullPointerException(空指针)的方法总结Java应用中抛出的空指针异常是解决空指针的最好方式,也是写出
- cookie机制和session机制的区别具体来说cookie机制采用的是在客户端保持状态的方案,而session机制采用的是在服务器端保持
- 前言:2022年Java将有什么新的特性和改进,我相信很多Java开发者都想知道。结合Java语言架构师布莱恩·格茨(
- 本文实例讲述了C#清除字符串内空格的方法,分享给大家供大家参考。具体如下:关键代码如下:/// <summary>/// 清除字
- 本文实例讲述了c#窗体传值用法。分享给大家供大家参考。具体分析如下:对于窗体间的数据传递,是刚开始从事.Net窗体应用程序开发人员碰到的一个
- 每次写批量的时候,都要在网上搜索一下,虽然都做过多次了,但具体的自己还是记不住(汗颜),所以索性今天就记录下来。前期说明:foreach的主
- 1.饿汉模式饿汉模式也叫预加载模式,它是在类加载时直接创建并初始化单例对象,所以它并不存在线程安全的问题。它是依靠 ClassLoader
- 项目需要对接外部接口,将图片文件流发送到外部接口,下面代码就是HttpsURLConnection如何上传文件流:/** *
- 一 概述DiffUtil是support-v7:24.2.0中的新工具类,它用来比较两个数据集,寻找出旧数据集-》新数据集的最小变化量。 说
- 前言:OpenFeign 是 Spring 官方推出的一种声明式服务调用和负载均衡组件。它的出现就是为了替代已经进入停更维护状态的 Feig
- 举个例子Map < String , Object > jsonMap = new HashMap< String , O
- 1、SpringBoot配置文件1.1 优先级关于SpringBoot配置文件可以是properties或者是yaml格式的文件,但是在Sp
- 定时任务1import lombok.extern.slf4j.Slf4j;/** * @author Created by niugang
- Android超清晰6.0权限申请AndPermission的具体实现代码,供大家参考,具体内容如下前言这是我经常使用的框架,原因:1.思路
- 本文实例为大家分享了Java实现简单贪吃蛇游戏的具体代码,供大家参考,具体内容如下贪吃蛇小游戏制作方法首先需要的准备有:1、掌握Java基础
- 目录前言1、饿汉式(线程安全)⭐2、懒汉式(线程不安全)⭐3、懒汉式(加锁)4、懒汉式(双重校验锁)⭐5、单例模式(静态内部类)6、单例模式
- 该配置基于IDEA2020.1版本,如后续有版本更新或者配置变更,再更新idea64.exe.vmoptions配置为提供IDEA启动速度和
- Java在控制台打印本月日历在学习《Java核心技术卷I·基础知识》第10版 的时候里面有一个小例子,就是在控制台上打印日历的一个例子,就想
- 要想了解Java * ,首先要了解什么叫做代理,熟悉设计模式的朋友一定知道在Gof总结的23种设计模式中,有一种叫做代理(Proxy)的对