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;
}
}