This article mainly introduces relevant information about the examples of Java's implementation of Dijkstra's output shortest path. I hope this article can help everyone. Friends in need can refer to
Java's implementation of Dijkstra's output specified starting point. The shortest path to the end point
Preface:
I recently participated in a competition in the company, and a problem involved can be simplified to the following description: a two dimensional matrix, each point has a weight, and you need to find the shortest path from a specified starting point to an end point.
I immediately thought of the Dijkstra algorithm, so I reviewed it again. Here is the Java implementation.
When outputting the shortest path, I also checked online and found no standard method, so in the following implementation, I gave a simpler method that I could think of. : Use the prev[] array for recursive output.
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;
}
}The above is the detailed content of Introduction to Java's method of implementing Dijkstra's output of the shortest path. For more information, please follow other related articles on the PHP Chinese website!