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;
}
}
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望通过本文能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
android sdk源码 andoid-21 下的TextUtils.java文本工具类 源码赏析
地理坐标（WGS84），投影坐标下（Mercator）切片系统的计算Java类
荐 JavaWeb~简单认识以太网、MAC地址、MTU机制、ARP协议、DNS协议
HUAWEI MH5000-31 LGA Module Hardware Guide draft
网友评论