Java实现Dijkstra输出最短路径的实例

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 indexPointMap; // 标号和点的对应关系

private Map pointIndexMap; // 点和标号的对应关系

private int v0; // 起点标号

private Point startPoint; // 起点

private Point endPoint; // 终点

private Map pointPointMap; // 保存点和权重的映射关系

private List 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 getAroundPoints(Point point) {

List 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) {

rkawyjSIrW 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 http://

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;

}

}

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望通过本文能帮助到大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。